#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/15/problems/G

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Complementary Path - Repovive Starter Round 4 | Repovive | Repovive

15G. Complementary Path

3500 pts1s256 MB

You are given the complement of a simple undirected graph $G$ .

More precisely, the input graph is a graph $\overline{G}$ on vertices $1,2,\ldots,n$ .
For every two distinct vertices $u$ and $v$ , the edge $(u,v)$ exists in $G$ if and only if it does not exist in $\overline{G}$ .

The input graph $\overline{G}$ has no triangle. In other words, there are no three distinct vertices $a$ , $b$ , and $c$ such that all three edges $(a,b)$ , $(b,c)$ , and $(c,a)$ exist in the input graph.

For each test case, find a Hamiltonian path in $G$ , or determine that no such path exists.

A Hamiltonian path is an ordering of all $n$ vertices $p_1,p_2,\ldots,p_n$ such that for every $1 \le i < n$ , the edge $(p_i,p_{i+1})$ exists in $G$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le 2 \times 10^5$
The input graph is simple and undirected.
The input graph has no triangle.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

For each test case, if there is no Hamiltonian path in $G$ , output

\text{No}

Otherwise, output

\begin{array}{l} \text{Yes} \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array}

where $p_1,p_2,\ldots,p_n$ is a Hamiltonian path in $G$ .

You may print each letter in any case.

Samples

Input

Case 1

1 0

Case 2

3 2
1 2
2 3

Case 3

4 0

Case 4

Case 5

Explanation

Case 1

The only vertex is already a Hamiltonian path.

Case 2

In the complement graph, vertex $2$ is isolated, so no Hamiltonian path can use all vertices.

Case 3

The given graph has no edges, so its complement is complete. The printed ordering is therefore valid.

Case 4

The complement graph has only the edges $1$ - $2$ and $3$ - $4$ , so it is disconnected and cannot have a Hamiltonian path.

Case 5

For the printed ordering, every consecutive pair is a non-edge of the given graph, so every consecutive pair is an edge of its complement.

Output

Case 1

Yes
1

Case 2

No

Case 3

Yes
4 3 2 1

Case 4

No

Case 5

Yes
2 5 3 1 4

You are given the complement of a simple undirected graph $G$ .

For each test case, find a Hamiltonian path in $G$ , or determine that no such path exists.

A Hamiltonian path is an ordering of all $n$ vertices $p_1,p_2,\ldots,p_n$ such that for every $1 \le i < n$ , the edge $(p_i,p_{i+1})$ exists in $G$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le 2 \times 10^5$
The input graph is simple and undirected.
The input graph has no triangle.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

For each test case, if there is no Hamiltonian path in $G$ , output

\text{No}

Otherwise, output

\begin{array}{l} \text{Yes} \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array}

where $p_1,p_2,\ldots,p_n$ is a Hamiltonian path in $G$ .

You may print each letter in any case.

In the complement graph, vertex $2$ is isolated, so no Hamiltonian path can use all vertices.

The complement graph has only the edges $1$ - $2$ and $3$ - $4$ , so it is disconnected and cannot have a Hamiltonian path.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

15G. Complementary Path

Constraints

Input

Output

Samples

15G. Complementary Path

Constraints

Input

Output

Samples