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

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

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

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

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

Repovive

Graph Interval Connectivity - Repovive Premier Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

6G. Graph Interval Connectivity

3500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given a graph with $n$ vertices. Initially, the graph has no edges.

You are also given $m$ operations. In the $i$ -th operation, three integers $l_i$ , $v_i$ , and $r_i$ are given, where $l_i \le v_i \le r_i$ .

For each operation, you must choose an integer $u_i$ such that $l_i \le u_i \le r_i$ , and then add an undirected edge between $v_i$ and $u_i$ .

The graph may contain self-loops and multiple edges.

Determine whether it is possible to choose all values $u_1,u_2,\ldots,u_m$ so that the final graph is connected. If it is possible, output one valid choice.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \cdot 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le l_i \le v_i \le r_i \le n$
The sum of $n$ over all test cases is at most $2 \cdot 10^5$
The sum of $m$ over all test cases is at most $2 \cdot 10^5$

Input

t

\left. \begin{array}{l} n \quad m \\ l_1 \quad v_1 \quad r_1 \\ l_2 \quad v_2 \quad r_2 \\ \vdots \\ l_m \quad v_m \quad r_m \end{array} \right\} \times t

Output

For each test case, if it is impossible to make the graph connected, output

\begin{array}{l} \texttt{No} \end{array}

Otherwise, output two lines in the following format:

\begin{array}{l} \texttt{Yes} \\ u_1 \quad u_2 \quad \cdots \quad u_m \end{array}

where $l_i \le u_i \le r_i$ for every $i$ , and the graph formed by the edges $(v_i,u_i)$ is connected.

If there are multiple valid answers, you may output any of them.

Samples

Input

Case 1

1 2
1 1 1
1 1 1

Case 2

2 1
1 1 2

Case 3

3 2
1 1 2
2 2 3

Case 4

4 2
1 1 2
3 3 4

Case 5

Explanation

Case 1

The graph has only one vertex, so it is already connected. Both operations add self-loops.

Case 2

Choosing $u_1=2$ adds the edge between vertices $1$ and $2$ , so the graph becomes connected.

Case 3

Choosing $u_1=2$ and $u_2=3$ adds the edges $(1,2)$ and $(2,3)$ , so all three vertices are connected.

Case 4

The first operation can only use vertices from $1$ to $2$ , and the second operation can only use vertices from $3$ to $4$ . Therefore no edge can connect the two parts $\{1,2\}$ and $\{3,4\}$ .

Case 5

One valid choice is $u=(1,4,4,1,2,5)$ . The added edges include $(3,1)$ , $(2,4)$ , $(5,4)$ , and $(3,2)$ , which connect all five vertices.

Output

Case 1

Yes
1 1

Case 2

Yes
2

Case 3

Yes
2 3

Case 4

No

Case 5

Yes
1 4 4 1 2 5

You are given a graph with $n$ vertices. Initially, the graph has no edges.

You are also given $m$ operations. In the $i$ -th operation, three integers $l_i$ , $v_i$ , and $r_i$ are given, where $l_i \le v_i \le r_i$ .

For each operation, you must choose an integer $u_i$ such that $l_i \le u_i \le r_i$ , and then add an undirected edge between $v_i$ and $u_i$ .

The graph may contain self-loops and multiple edges.

Determine whether it is possible to choose all values $u_1,u_2,\ldots,u_m$ so that the final graph is connected. If it is possible, output one valid choice.

$1 \le t \le 10^4$
$1 \le n \le 2 \cdot 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le l_i \le v_i \le r_i \le n$
The sum of $n$ over all test cases is at most $2 \cdot 10^5$
The sum of $m$ over all test cases is at most $2 \cdot 10^5$

t

\left. \begin{array}{l} n \quad m \\ l_1 \quad v_1 \quad r_1 \\ l_2 \quad v_2 \quad r_2 \\ \vdots \\ l_m \quad v_m \quad r_m \end{array} \right\} \times t

For each test case, if it is impossible to make the graph connected, output

\begin{array}{l} \texttt{No} \end{array}

Otherwise, output two lines in the following format:

\begin{array}{l} \texttt{Yes} \\ u_1 \quad u_2 \quad \cdots \quad u_m \end{array}

where $l_i \le u_i \le r_i$ for every $i$ , and the graph formed by the edges $(v_i,u_i)$ is connected.

If there are multiple valid answers, you may output any of them.

Choosing $u_1=2$ adds the edge between vertices $1$ and $2$ , so the graph becomes connected.

Choosing $u_1=2$ and $u_2=3$ adds the edges $(1,2)$ and $(2,3)$ , so all three vertices are connected.

The first operation can only use vertices from $1$ to $2$ , and the second operation can only use vertices from $3$ to $4$ . Therefore no edge can connect the two parts $\{1,2\}$ and $\{3,4\}$ .

One valid choice is $u=(1,4,4,1,2,5)$ . The added edges include $(3,1)$ , $(2,4)$ , $(5,4)$ , and $(3,2)$ , which connect all five vertices.