CF2245D2 Construct an Array (Hard Version)

此题是该问题的困难版本。两个版本的区别在于，此版本中 $n \le 2 \times 10^5,0 \le m \le \min(10^6,\frac{n(n+1)}{2})$。 给出两个整数 $n$ 和 $m$，您需要构造出一个长度为 $n$ 满足 $m$ 条限制的整数数组 $a$。每个限制可以由元组 $(o,i,j)$ 表示，其中 $o \in \{1,2\},1 \le i \le j \le n$： - 如果 $o=1$，那么 $a_i+a_j \ge 0$。 - 如果 $o=2$，那么 $a_i+a_j < 0$。

每个测试包含多个测试用例。 第一行包含一个整数 $t\ (1 \le t \le 10^4)$——测试用例的数量，测试用例的描述如下： 每个测试用例的第一行包含两个整数 $n$ 和 $m\ (n \le 2 \times 10^5,0 \le m \le \min(10^6,\frac{n(n+1)}{2}))$——分别表示需要构造的数组 $a$ 的长度和限制数量。 接下来 $m$ 行每一行包含三个整数 $o$、$i$ 和 $j\ (o \in \{1,2\},1 \le i \le j \le n)$——表示每一个限制，保证每一对整数 $i$ 和 $j$ 最多出现在一个限制条件中。

对于每个测试用例，如果不存在这样的数组 $a$，则输出 `NO`。 否则，首先单行输出 `YES`，然后输出 $n$ 个整数 $a_1,a_2,\dots,a_n\ (|a_i| \le 10^9)$。可以证明，在问题的约束下，如果存在这样一个数组，那么数组中所有元素的绝对值都不超过 $10^9$。 如果存在多个满足要求的数组，您可以输出其中任意一个。 您可以输出任何大小写（大写或小写）的答案。例如，字符串 `yEs`、`yes`、`Yes` 和 `YES` 均被视为肯定回答。

在第一个测试用例中，唯一的限制条件是 $a_1+a_1 \ge 0$，这意味着 $a_1 \ge 0$，因此 $a_1$ 可是任意非负整数。 在第二个测试用例中，唯一的限制条件是 $a_1+a_1 < 0$，这意味着 $a_1 < 0$，因此 $a_1$ 可是任意负整数。 在第四个测试用例中，第一个和第二个限制条件意味着 $a_1,a_2 \ge 0$，但是第三个限制条件意味着 $a_1+a_2 < 0$，这就产生了矛盾。 在第九个测试用例中，没有任何限制条件，因此任何整数数组 $a$ 都是正确的。 在第十个测试用例中，$[6,-6,4,-4,2,-2,0]$ 是一个有效的解，注意 $[7,−6,5,−4,3,−2,1]$ 也是一个有效的解。