EVENCYCLE

Problem

Given an undirected graph consisting of ~N~ vertices and ~M~ edges, find a cycle with an even number of edges, if it exists.

Input:

The first line of the input will contain a positive integer ~T~, the number of queries to answer. Each of the next ~T~ queries will begin with a line containing two natural numbers ~N~ and ~M~ separated by a space: the number of vertices and the number of edges of the graph. Following this, there will be ~M~ lines, each containing two natural numbers ~U~ and ~V~ separated by a space, representing an edge between vertices ~U~ and ~V~. Assume vertices are numbered from ~1~ to ~N~, and no two edges connecting the same pair of vertices in the graph will be given.

Output:

The output should contain exactly ~T~ lines, each one corresponding to an answer to a query in the order they are given. Each answer line will contain either:

• The word "cycle", followed by an even positive integer ~K~ (the number of edges in the cycle), followed by ~K~ integers ~u_1~, ~u_2~, ~...~, ~u_K~. This answer indicates that the requested cycle has been found. To be valid, such an answer must satisfy ~K \ge 4~ (as a single edge is not considered a cycle), the numbers ~u_1~, ~u_2~, ~...~, ~u_K~ must be pairwise distinct vertices of the cycle, there must be an edge (~u_i~,\; ~u_{i+1}~) for each ~1 \le i < K~, and there must also be an edge ~(u_K,; u_1)~ to complete the cycle. If there are multiple cycles with an even number of edges, you may print any of them.
• The word "none", if there is no cycle with an even number of edges. All words and numbers on each line of the output should be separated in pairs by a single space.

Constraints

• ~1 \le T \le 10~
• ~1 \le N \le 100.000~ and ~0 \le M \le 200.000~. Of course, it will be true that ~M \le N *\frac{(N - 1)}{2}~.
• ~1 \le U \le N~ and ~1 \le V \le N~ for every edge given, and also ~U \neq V~.
• The sum of all ~N~ queries will not exceed ~200.000~, and the sum of all ~M~ queries will not exceed ~400.000~.
• Time Limit: ~1~ sec.

• Memory Limit: ~256~ MB.

• For test cases with a total value of ~15%~, it will be ~N \le 10~.

• For test cases with a total value of ~15%~, it will be ~10 < N \le 100~ and ~M \le 200~.
• For test cases with a total value of ~22%~, the vertices of the graph can be colored using two colors in such a way that there are no edges between vertices of the same color.
• For test cases with a total value of ~11%~, each vertex of the graph will be connected to at most two other vertices.
• For test cases with a total value of ~15%~, each vertex of the graph will be connected to at most three other vertices (and there will be vertices that are connected exactly to three other vertices.).
• For the rest of the test cases with a total value of ~22%~, none of the above special constraints will apply..

Example of Input - Output Files:

Note: For your convenience, in the example that follows, the three input queries are separated from each other.

evencycle.in	evencycle.out
~3~
4 5 1 2 1 3 2 3 3 4 4 1	cycle 4 3 2 1 4
5 6 1 2 1 3 1 4 1 5 2 3 4 5	none
7 6 1 7 3 4 4 5 5 6 6 3 5 2	cycle 4 6 3 4 5