Beautiful Walk

All submissions for this problem are available.
You are given a directed graph with $n$ vertices and $m$ edges. A walk is defined as a sequence of vertices, such that there is an edge from every vertex in the walk to the next vertex in the walk. Formally, a walk with $t$ edges is a sequence $v_1, v_2, \ldots v_{t+1}$, where for each $1 \leq i \leq t$, there is an edge from $v_i$ to $v_{i + 1}$. The vertices $v_i$ of a walk do *not* have to be distinct. A single edge can occur multiple times in a walk. Call a walk beautiful if it has atmost $ \left \lfloor \frac{n^2}{4} \right \rfloor $ edges and each vertex is present in it at least once. There are multiple independent testcases. For each testcase, find a beautiful walk in the given graph or claim that it doesn't exist. ### Input  First line will contain $T$, number of testcases. Then the testcases follow.  The first line of each testcase contains of $n$ and $m$, the number of vertices and the number of edges in the graph respectively.  The next $m$ lines describe the edges of the graph. Each line consists of two integers $a$ and $b$ denoting a directed edge from $a$ to $b$. ### Output For each testcase:  If there doesn't exist a beautiful walk, print $1$ on a newline.  If there exists a beautiful walk, find any such walk. Say it has $l \leq \frac{n^2}{4}$ edges, and the sequence of vertices is $\{v_1, v_2, \ldots v_{l + 1} \}$. Print $l$ followed by $v_1, v_2, \ldots v_{l + 1}$ on a new line. ### Constraints  $1 \leq T \leq 1000$  $2 \leq n \leq 1000$  $ 0 \leq m \leq \min(n (n  1), 10^4)$  The sum of $n$ over all testcases doesn't exceed $1000$.  There are no multiple edges in the input. Note that it is allowed to have an edge from $i$ to $j$ and another from $j$ to $i$ though. ### Example Input ``` 2 5 6 1 2 2 3 3 1 1 4 4 5 5 1 3 2 1 2 1 3 ``` ### Example Output ``` 5 1 2 3 1 4 5 1 ``` ### Explanation In the first testcase, the walk $1 \rightarrow 2 \rightarrow 3 \rightarrow1 \rightarrow 4 \rightarrow 5$ is a beautiful walk, as it visits all vertices and has $5 \leq \frac{5^2}{4}$ edges. Note that `5 1 4 5 1 2 3` is also a valid output. In the second test case, there is no beautiful walk, so you sould print $1$.Author:  jtnydv25 
Tags  graphtheory, jtnydv25, mediumhard 
Date Added:  10122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, 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. 