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

Graph Interval Connectivity - Repovive Premier Round 3 | Repovive

6G. Graph Interval Connectivity

3500 pts2s256 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.

	#	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

6G. Graph Interval Connectivity

Constraints

Input

Output

Samples

6G. Graph Interval Connectivity

Constraints

Input

Output

Samples