Complementary Path - Repovive Starter Round 4 | 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.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

15G. Complementary Path

Constraints

Input

Output

Samples

15G. Complementary Path

Constraints

Input

Output

Samples