Solve what you want
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.Gleb is trying to solve the **P versus NP** problem, so he is doing some research now. He does not have time to solve boring and easy problems like this one, so he gave it to you. You are given a connected undirected graph with $N$ vertices labelled $1$ through $N$ and a number $K$. You have to solve exactly one of the following two problems or determine that both of them have no solution (if both have a solution, you are free to choose either one of them to solve): - Find a cut in the graph with size strictly smaller than $K$. A *cut* is a partition of vertices of the graph into two non-empty subsets $A$ and $B$ ($A \cap B = \emptyset$, $|A| + |B| = N$). The *size* of a cut is the number of edges $(u, v)$ such that $u \in A$ and $v \in B$. - Find a simple cycle in the graph with *size* at least $K$ (containing at least $K$ vertices). A simple cycle does not visit any edge more than once and does not visit any vertex more than once. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains three space-separated integers $N$, $M$ and $K$. - Each of the following $M$ lines contains two space-separated integers $u$ and $v$ describing an edge between vertices $u$ and $v$. ### Output For each test case: - If both problems have no solution, print a single line containing the string `"NO ANSWER"`. - Otherwise, print three lines. The first line should contain the string `"CUT"` if you solved the first problem or `"CYCLE"` if you solved the second problem. - If you solved the first problem, the second line should contain a single integer — the size of the set $A$, and the third line should contain $|A|$ space-separated integers denoting the labels of vertices in the set $A$. - If you solved the second problem, the second line should contain a single integer — the size $S$ of the simple cycle you found, and the third line should contain $S$ space-separated integers denoting the vertices of the cycle in an order in which they appear on the cycle. ### Constraints - $1 \le T \le 100$ - $2 \le N, M \le 2 \cdot 10^5$ - $3 \le K \le N$ - $1 \le u, v \le N$ - $u \neq v$ for each edge - there are no two edges connecting the same pair of vertices - the graph described on the input is connected - the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$ - the sum of $M$ over all test cases does not exceed $2 \cdot 10^5$ ### Subtasks **Subtask #1 (40 points):** $1 \le N \le 10$ **Subtask #2 (60 points):** original constraints ### Example Input ``` 2 8 7 3 1 4 2 4 3 4 4 5 5 6 5 7 5 8 3 3 3 1 2 2 3 1 3 ``` ### Example Output ``` CUT 4 1 2 3 4 CYCLE 3 1 2 3 ```
|Tags||altruist_, dfs, graph-theory, ltime59, medium, np-hard|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.