All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Given a bipartite graph of N vertices in which every vertex has degree exactly 3, find a set of distinct simple cycles such that every edge belongs to exactly two cycles. The vertices are numbered from 1 to N. For the given constraints, it can be shown that such a set of cycles always exists.
A simple cycle of length k (k must be at least 3) in the graph is a sequence of vertices v1, v2, .., vk, such that vi ≠ vj if i ≠ j, and such that there exist edges between vertex vi and vi + 1 for i < k, and an edge between vertices vk and v1.
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains one integer N, denoting the number of vertices in the graph.
Each of the next 3 × N/2 lines contains two integers u, v, denoting an edge of the graph.
For each test case describe any valid set of cycles. First print C, the number of cycles.
In the next C lines describe one cycle per line: the i-th line should contain an integer ki, denoting the number of vertices in the i-th cycle, followed by ki space separated integers, which should be the sequence of vertices of the cycle in order.
- 6 ≤ N ≤ 105
- N is an even integer
- 1 ≤ u, v ≤ N
- The sum of N over all test cases is at most 5 × 105
- The graph is guaranteed to be bipartite, and every vertex will have degree exactly 3
- The graph will not have multi-edges or loops
Input: 1 6 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 Output: 3 6 3 6 2 5 1 4 6 3 5 2 4 1 6 6 3 5 1 6 2 4
The following image depicts the three cycles in the output of the sample case. Note that for every edge in the original graph, there are two cycles that contain it.
|Time Limit:||3.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.