using System;
using System.Collections.Generic;
using System.Linq;
namespace DAG
{
public static class DAG
{
static void Main(string[] args)
{
var deps = new List<Tuple<char, char>>();
#if false
deps.Add(new Tuple<char, char>('A', 'B'));
deps.Add(new Tuple<char, char>('B', 'C'));
deps.Add(new Tuple<char, char>('A', 'C'));
deps.Add(new Tuple<char, char>('A', 'D'));
deps.Add(new Tuple<char, char>('C', 'D'));
#elif false
deps.Add(new Tuple<char, char>('A', 'B'));
deps.Add(new Tuple<char, char>('A', 'C'));
deps.Add(new Tuple<char, char>('B', 'C'));
deps.Add(new Tuple<char, char>('B', 'D'));
deps.Add(new Tuple<char, char>('D', 'A'));
deps.Add(new Tuple<char, char>('D', 'C'));
#else
deps.Add(new Tuple<char, char>('A', 'B'));
deps.Add(new Tuple<char, char>('B', 'C'));
deps.Add(new Tuple<char, char>('C', 'D'));
deps.Add(new Tuple<char, char>('D', 'E'));
deps.Add(new Tuple<char, char>('E', 'F'));
deps.Add(new Tuple<char, char>('F', 'G'));
deps.Add(new Tuple<char, char>('G', 'H'));
deps.Add(new Tuple<char, char>('H', 'F'));
#endif
while (true)
{
foreach (var t in deps)
Console.WriteLine(t.Item1 + "->" + t.Item2);
Console.WriteLine();
var parent = new HashSet<char>();
var child = new HashSet<char>();
foreach (var t in deps)
{
parent.Add(t.Item1);
child.Add(t.Item2);
}
var dif = parent.Except(child);
if (dif.Count() == 0)
break;
deps.RemoveAll(t => dif.Contains(t.Item1) || dif.Contains(t.Item2));
}
if (deps.Count == 0)
Console.WriteLine("DAG!!");
else
Console.WriteLine("cyclic!!");
}
}
}