U398693 QAQ【Part 1】

本题对应测试点1-15，满分75。 [其他测试点在此处](https://www.luogu.com.cn/problem/U398694)

有 $n$ 个人正在发癫，已知有 $m$ 个它们可能对着发癫的 Vtuber 且每个人有两个推的 Vtuber ，保证这两位 Vtuber 不同且没有任意两个人推的两位 Vtuber 完全一致，这些人只有可能对着自己推的 Vtuber 发癫。 试问有没有可能每个人对着发癫的 Vtuber 各不相同，若有，请给出一种可能的情况。

本题每个测试点有多组测试数据。 输入文件的第一行为一个正整数 $T$ 表示测试数据组数。 对于每组测试数据： 第一行两个数 $n,m$ 分别表示有多少个人发癫以及他们发癫可能涉及到的 Vtuber 总数。 接下来 $n$ 行每行两个正整数 $x,y$，第 $i$ 行的这两个数分别记为 $x_i,y_i$，为第 $i$ 个人推的两位 Vtuber 的编号。

对于每组测试数据： 若不存在任意一种可能性使每个人对着发癫的 Vtuber 各不相同，输出一行一个字符串 ```NO``` 。 否则，输出两行： 第一行为一个字符串 ```YES``` 。 第二行为 $n$ 个空格分隔的正整数表示一种可能性，第 $i$ 个数 $a_i$ 代表第 $i$ 个人此时对着编号为 $a_i$ 的 Vtuber 发癫。 本题使用 **Special Judge**，若有多种可能性，输出其中一种即可。

记一个测试点中全部的 $T$ 组测试数据的 $n$ 的总和为 $\sum n$，$m$ 的总和为 $\sum m$。 对于所有测试点，保证 $1 \le n\le 10^6,2 \le m\le 10^6,T\le 10^5,\sum n,\sum m \le 2\times 10 ^6$，$\forall i\in[1,n],x_i\ne y_i,1\le x_i,y_i\le m$ 且 $\forall i,j\in[1,n] $ 且 $ i\ne j$，记 $a_i=\min\{x_i,y_i\},b_i=\max\{x_i,y_i\}$，其中 $min\{a,b\}$ 与 $max\{a,b\}$ 分别为 $\{a,b\}$ 中的较小 $/$ 较大者，有 $a_i\ne a_j$ 与 $b_i\ne b_j$ 中的至少一条成立。 | 测试点编号 | $n$ | $m$ | $\sum n$ | $\sum m$ | $T$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\le10$ | $\le10$ | $\le10$ | $\le10$ | $=1$ | 无 | | $2$ | $\le8$ | $\le8$ | $\le20$ | $\le20$ | $=3$ | 无 | | $3$ | $\le8$ | $\le8$ | $\le5\times 10^5$ | $\le5\times10^5$ | $\le10^5$ | 无 | | $4$ | $\le20$ | $\le20$ | $20$ | $20$ | $=1$ | 无 | | $5$ | $\le20$ | $\le20$ | $200$ | $200$ | $=10$ | 无 | | $6$ | $\le500$ | $\le500$ | $\le 3000$ | $\le 3000$ | $\le 10$ | $A$ | | $7$ | $\le500$ | $\le500$ | $\le 3000$ | $\le 3000$ | $= 6$ | $B$ | | $8$ | $\le500$ | $\le500$ | $\le 3000$ | $\le 3000$ | $\le 10$ | 无 | | $9$ | $\le500$ | $\le500$ | $\le 1500$ | $\le 1500$ | $\le 500$ | 无 | | $10$ | $\le5000$ | $\le5000$ | $\le 1.5\times 10^4$ | $\le 1.5 \times 10^4$ | $\le 10^4$ | 无 | | $11$ | $\le5\times 10^4$ | $\le5\times 10^4$ | $\le5\times 10^4$ | $\le5\times 10^4$ | $=1$ | $A$ | | $12$ | $\le5\times 10^4$ | $\le5\times 10^4$ | $\le 10^6$ | $\le 10^6$ | $\le 5\times 10^4$ | $A$ | | $13-14$ | $\le10^5$ | $\le10^5$ | $\le5\times 10^5$ | $\le5\times 10^5$ | $\le 5\times 10^4$ | 无 | | $15$ | $\le10^6$ | $\le10^6$ | $\le2\times 10^6$ | $\le2\times 10^6$ | $= 2$ | $B$ | | $16$ | $\le10^6$ | $\le10^6$ | $\le2\times 10^6$ | $\le2\times 10^6$ | $\le 10^5$ | $A$ | | $17-20$ | $\le10^6$ | $\le10^6$ | $\le2\times 10^6$ | $\le2\times 10^6$ | $\le 10^5$ | 无 | 特殊性质 $A$：该测试点的全部测试数据均满足：每位 Vtuber 被最多 $2$ 个人对着发癫。 特殊性质 $B$：该测试点的全部测试数据均为随机生成。