Cycle Detection in Logicland's Road Network

In Logicland, the road network is modeled as a directed graph with (N) cities and (M) one-way roads. Each road is defined by three integers: the starting city, the ending city, and its weight (which can be ignored for the purpose of cycle detection). Your task is to determine whether there exists any cycle in the network. A cycle is defined as a sequence of cities (C_1, C_2, \dots, C_k) such that there is a road from (C_i) to (C_{i+1}) for (1 \le i < k) and a road from (C_k) back to (C_1) (i.e. (C_1 \rightarrow C_2 \rightarrow \cdots \rightarrow C_k \rightarrow C_1)).

If a cycle exists, print "CYCLE" on the first line, followed by a second line containing the sequence of cities constituting the cycle (in order). If there are multiple cycles, output any one of them. If no cycle is present, simply output "NO CYCLE".

inputFormat

The input is read from standard input (STDIN) and has the following format:

The first line contains two integers (N) and (M), representing the number of cities and the number of roads, respectively. Then (M) lines follow, each containing three integers (U), (V), and (W) which denotes there is a directed road from city (U) to city (V) with weight (W).

outputFormat

Print the result to standard output (STDOUT). If a cycle exists, the first line should be "CYCLE" and the second line should list the cities (space-separated) that form a cycle. If no cycle exists, print only "NO CYCLE".## sample

5 5
1 2 1
2 3 1
3 4 1
4 2 1
4 5 1

CYCLE
2 3 4