Decide whether any walk starting at intersection 1 in a directed graph can revisit an intersection.
Easy3DFSGraphInterviewNo attempts yetTime limit2sMemory limit256 MBIn the year 2050 an extremely strong storm hit Incheon. Everyone moved to a shelter and many roads were washed away. On the roads that are left, every sign and every street lamp stopped working, so finding the right way is close to impossible.
Minji wants to send relief supplies to the shelter. In 2050 the city of Incheon consists only of intersections and roads. One intersection is joined to another by a one way road, and several roads can leave the same intersection. Once a truck enters a road it cannot leave that road until it arrives at the next intersection.
Minji was ready to send out a truck loaded with supplies, but the drivers refused to go. The storm made the navigation systems inaccurate and broke the signs that told the roads apart, so a driver does not know which road to pick at an intersection. Picking a road at random can bring the truck back to an intersection it already passed, and then the truck runs out of fuel before it reaches the shelter.
Minji wants to convince the drivers by proving that on the way from intersection 1, where she is now, to intersection N, where the shelter is, no choice of roads ever returns to an intersection the truck already passed.

The picture above shows two possible layouts when the shelter sits at intersection 3. In the left one every choice of roads arrives at intersection 3 without passing an intersection twice. In the right one the truck can return to an intersection it already visited.
Help Minji and write a program that decides whether a truck starting at intersection 1 and picking roads at random can visit an intersection it already passed.
The first line contains the number of intersections N (1≤N≤100). The states of intersections 1 through N−1 follow in order, two lines per intersection. The first line holds the number of intersections joined to intersection i by a road, Mi (0≤Mi≤N), and the next line holds the Mi numbers Ci (1≤Ci≤N) of the intersections reachable from intersection i, separated by spaces. When Mi is 0 the next line is empty. Intersection N is where the shelter is, so its connections are not given. The supplies always start at intersection 1, and the shelter is always at intersection N.
Print CYCLE if a truck that starts at intersection 1 and picks roads can visit an intersection it already passed. Otherwise print NO CYCLE.