P13641 [NWRRC 2021] New White-Black Tree

Naomi 学习了红黑树，现在是学习白黑树的时候了。 她正在阅读一本算法书。有些页面上画有树的图，但这些树的边经过多年已经褪色了。根据正文，每条边应该是白色或黑色之一。 Naomi 注意到每个顶点旁边都写着两个整数。她猜测第一个整数表示与该顶点相连的白色边的数量，第二个整数表示与该顶点相连的黑色边的数量。 Naomi 重新绘制了所有的图。你能做到吗？

第一行包含一个整数 $t$，表示需要重建的图片数量（$1 \le t \le 3 \cdot 10^5$）。 接下来的若干行描述 $t$ 张图片。每张图片的描述以一行整数 $n$ 开始，表示树的顶点数（$1 \le n \le 3 \cdot 10^5$）。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $w_i$ 和 $b_i$，分别表示写在第 $i$ 个顶点旁的白色边和黑色边的数量（$0 \le w_i, b_i \le n - 1$）。 保证所有图片的 $n$ 之和不超过 $3 \cdot 10^5$。

输出 $t$ 个区块，第 $i$ 个区块描述第 $i$ 张图片的重建情况。 每个区块的第一行输出 $\tt{No}$，如果无法重建；如果至少有一种重建方式，则输出 $\tt{Yes}$。如果可以重建该树，则再输出 $n-1$ 行，每行包含两个整数和一个字母 $\tt{W}$ 或 $\tt{B}$，分别表示一条连接顶点 $v_i$ 和 $u_i$ 的边及其颜色（$1 \le v_i, u_i \le n$；$c_i$ 为 $\tt{W}$ 或 $\tt{B}$）。 如果有多种重建方式，可以输出任意一种。树的边可以按任意顺序输出。

由 ChatGPT 4.1 翻译