Timeless Overtakes - Repovive Premier Round 7 | Repovive

20B. Timeless Overtakes

1000 pts2s256 MB

At the beginning of a race, the order of $n$ cars from front to back is $1, 2, \ldots, n.$

An overtake can happen only when two cars are adjacent. The car behind moves in front of the other car, so the two cars swap positions. Moreover, every pair of cars passes each other at most once.

A camera recorded all $m$ overtakes, but their timestamps were lost. Each report $(x,y)$ states that car $x$ overtook car $y$ .

Determine whether the reports can be arranged in a chronological order such that exactly these overtakes could have happened. If they can, also find the order of the cars from front to back at the end of the race.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le \min\left(2 \times 10^5, \frac{n(n-1)}{2}\right)$
$1 \le y_i < x_i \le n$
No pair $(x_i,y_i)$ appears more than once in the same test case
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 \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_m \quad y_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{No} \end{array} \quad\text{or}\quad \begin{array}{l} \text{Yes} \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

For each test case, print No if the reports cannot all be realized.

Otherwise, print Yes on the first line. On the second line, print a permutation $p_1,p_2,\ldots,p_n$ : the order of the cars from front to back after all reported overtakes.

The words Yes and No are case-insensitive. For example, YES, yes, and yEs are all accepted.

Samples

Input

Case 1

1 0

Case 2

3 2
2 1
3 2

Case 3

Case 4

5 0

Case 5

Explanation

Case 1

With only one car and no reports, the final order remains $1$ .

Case 2

The reports require car $3$ to finish in front of car $2$ , and car $2$ to finish in front of car $1$ . However, cars $3$ and $1$ did not pass each other, so car $1$ would have to remain in front of car $3$ . These requirements are contradictory.

Case 3

The overtakes can happen in the order $(3,2)$ , $(3,1)$ , and $(4,2)$ . The resulting order is $3,1,4,2$ .

Case 4

No car overtakes another, so the initial order does not change.

Case 5

One possible chronological order of the reports is $(2,1)$ , $(5,4)$ , $(5,3)$ , and $(5,1)$ . The cars then finish in the order $2,5,1,3,4$ .

Output

Case 1

Yes
1

Case 2

No

Case 3

Yes
3 1 4 2

Case 4

Yes
1 2 3 4 5

Case 5

Yes
2 5 1 3 4

At the beginning of a race, the order of $n$ cars from front to back is $1, 2, \ldots, n.$

An overtake can happen only when two cars are adjacent. The car behind moves in front of the other car, so the two cars swap positions. Moreover, every pair of cars passes each other at most once.

A camera recorded all $m$ overtakes, but their timestamps were lost. Each report $(x,y)$ states that car $x$ overtook car $y$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le \min\left(2 \times 10^5, \frac{n(n-1)}{2}\right)$
$1 \le y_i < x_i \le n$
No pair $(x_i,y_i)$ appears more than once in the same test case
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 \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_m \quad y_m \end{array} \right\} \times t

\left. \begin{array}{l} \text{No} \end{array} \quad\text{or}\quad \begin{array}{l} \text{Yes} \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

For each test case, print No if the reports cannot all be realized.

Otherwise, print Yes on the first line. On the second line, print a permutation $p_1,p_2,\ldots,p_n$ : the order of the cars from front to back after all reported overtakes.

The words Yes and No are case-insensitive. For example, YES, yes, and yEs are all accepted.

With only one car and no reports, the final order remains $1$ .

The overtakes can happen in the order $(3,2)$ , $(3,1)$ , and $(4,2)$ . The resulting order is $3,1,4,2$ .

One possible chronological order of the reports is $(2,1)$ , $(5,4)$ , $(5,3)$ , and $(5,1)$ . The cars then finish in the order $2,5,1,3,4$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

20B. Timeless Overtakes

Constraints

Input

Output

Samples

20B. Timeless Overtakes

Constraints

Input

Output

Samples