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 nonempty 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 spaceseparated integers $N$, $M$ and $K$.  Each of the following $M$ lines contains two spaceseparated 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$ spaceseparated 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$ spaceseparated 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 ```Author:  altruist_ 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/NPORP 
Tags  altruist_, dfs, graphtheory, ltime59, medium, nphard 
Date Added:  20042018 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 