Rooted Tree Graph

All submissions for this problem are available.
Suppose that we have a rooted tree $T$ with vertices $1, \ldots, n$. We construct an undirected ancestor graph $G$ of $T$ with the same set of vertices. A pair of distinct vertices $v, u$ is adjacent in $G$ if and only if $v$ is an ancestor of $u$ in $T$, or vice versa. You are given a graph $G$ with $n$ vertices. Construct any rooted tree $T$ such that $G$ is the ancestor graph of $T$, or determine that no such $T$ exists. ###Input:  The first line contains a single integer $Q$, the number of test cases. $Q$ test case descriptions follow.  Each test case description starts with a line containing two integers, $n$ and $m$, the number of vertices and edges of the graph $G$ respectively.  The $i$th of the following $m$ lines describes the $i$th edge of $G$. It contains two integers, $u_i, v_i$ ($1 \leq u_i, v_i \leq n$), the endpoints of the $i$th edge. ###Output: For each test case:  If there is no suitable rooted tree $T$, print a single line containing the word `NO`.  Otherwise, on the first line print `YES`, and in the next line, print $n$ integers $p_1, \ldots, p_n$ describing the tree $T$. $p_i$ should be equal to the index of the parent vertex of $i$, or $0$ if vertex $i$ is the root. The numbers should describe a valid rooted tree, that is, there should be exactly one root vertex which should be an ancestor of any other vertex. If there are multiple suitable trees, output any of them. ###Constraints:  $1 \leq Q \leq 10^5$  $1 \leq n \leq 10^5$  $0 \leq m \leq 10^5$  The sum of $n$ over all testcases doesn't exceed $5 \cdot 10^5$  The sum of $m$ over all testcases doesn't exceed $5 \cdot 10^5$  The graphs described in the input do not contain selfloops or multiple edges. ###Sample Input: 5 1 0 3 2 1 2 2 3 3 3 1 2 1 3 2 3 4 2 1 4 2 3 7 10 1 2 1 3 2 4 2 5 3 6 3 7 1 4 1 5 1 6 1 7 ###Sample Output: YES 0 YES 2 0 2 YES 0 1 2 NO YES 0 1 1 2 2 3 3Author:  jtnydv25 
Tags  jtnydv25 
Date Added:  24122019 
Time Limit:  2 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. 