This is the hard version of the problem. The difference between the versions is that in this version, $$$n \le 2 \cdot 10^5$$$ and $$$0 \le m \le \min(10^6,\frac{n(n+1)}{2})$$$.

You are given two integers $$$n$$$ and $$$m$$$. You need to construct an integer array $$$a$$$ of length $$$n$$$ that satisfies $$$m$$$ restrictions. Each restriction can be represented by a tuple $$$(o,i,j)$$$ such that $$$o \in \{1,2\}$$$ and $$$1 \le i \le j \le n$$$:

If $$$o=1$$$, the sum $$$a_i+a_j$$$ must be non-negative.
If $$$o=2$$$, the sum $$$a_i+a_j$$$ must be negative.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le \color{red}{2 \cdot 10^5}$$$, $$$0 \le m \color{red}{\le} \min(10^6, \frac{n(n+1)}{2})$$$), representing the length of the array $$$a$$$ you need to construct and the number of restrictions, respectively.

Each of the next $$$m$$$ lines contains three integers $$$o$$$, $$$i$$$, and $$$j$$$ ($$$o \in \{1,2\}$$$, $$$1 \le i \le j \le n$$$), representing a restriction. It is guaranteed that each pair of integers $$$i$$$ and $$$j$$$ such that $$$1 \le i \le j \le n$$$ occurs in at most one restriction.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if no such array $$$a$$$ exists, output "NO".

Otherwise, first output "YES" on a single line. Then output $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i| \le 10^9$$$), representing the array $$$a$$$ you constructed. It can be proven that under the problem constraints, if such an array exists, there exists one where all elements in the array do not exceed $$$10^9$$$ in absolute value.

If there exist multiple arrays satisfying the requirement, you may output any of them.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note

In the first test case, the only restriction is that $$$a_1+a_1$$$ is non-negative, implying that $$$a_1$$$ is non-negative. Thus, $$$a_1$$$ can be any non-negative integer.

In the second test case, the only restriction is that $$$a_1+a_1$$$ is negative, implying that $$$a_1$$$ is negative. Thus, $$$a_1$$$ can be any negative integer.

In the fourth test case, the first and second restrictions imply that both $$$a_1$$$ and $$$a_2$$$ are non-negative. However, the third restriction forces $$$a_1+a_2$$$ to be negative, which leads to a contradiction.

In the ninth test case, there are no restrictions. Any integer array $$$a$$$ is valid.

In the tenth test case, $$$[6,-6,4,-4,2,-2,0]$$$ is a valid solution. Note that $$$[7,-6,5,-4, 3, -2,1]$$$ is also a valid solution.

#	Name	Rating↕	Solved↕
2245D2	Construct an Array (Hard Version) 2-sat constructive algorithms dfs and similar graphs implementation	unrated	1.7k
1697F	Too Many Constraints 2-sat constructive algorithms graphs implementation	2800	788
1567F	One-Four Overload 2-sat constructive algorithms dfs and similar dsu graphs implementation	2700	888

Problemset