An undirected graph is cylindrical if it can be split it into two disjoint simple cycles of equal length such that the ith node in the first cycle is connected to the ith node in the second cycle.
Given an undirected graph of even number of nodes n and 
edges, determine whether it is cylindrical or not, and if it is, print the two cycles that forms it (check the output section for the exact requirements).
The first line of input contains an even integer n (6 ≤ n ≤ 105), the number of nodes in the graph.
Each of the following lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), representing an edge connecting the nodes u and v. Each pair of nodes is connected by at most one edge.
Print "NO" if the given graph is not cylindrical. Otherwise, print "YES" followed by two lines, each containing the nodes of one cycle in following format:
c1 c2 ... 
- Each consecutive nodes in a cycle must be connected by an edge in the input. Also the first and the last nodes in the cycle must be connected.
- The ith node in the first cycle must be connected to the ith node in the second cycle.
- Each of the n nodes must belong to exactly one of the cycles.
If there is more than one solution, you can print any of them.
6
1 2
2 3
3 1
4 5
4 6
5 6
1 5
2 6
3 4
YES
1 3 2
5 4 6
6
2 6
3 6
1 3
2 1
3 4
4 2
4 5
5 6
1 5
NO
| 2018 PSUT Coding Marathon |
|---|
| Finished |
