4183. 「ROI 2024 Day2」交互式通道

时间限制：$1000 \text{ ms}$
内存限制：$512 \text{ MiB}$

题目描述

译自 ROI 2024 Day2 T2. Интерактивные переходы

因诺波利斯大学校园包括 $n$ 个建筑，通过 $m$ 条通道连接。每条通道连接两个不同的建筑，且任意两个建筑之间最多只有一条通道。

每座建筑都装有可以开启或关闭的灯光系统。初始时，所有建筑的灯光都是关闭的。管理员可以通过一个动作来开启或关闭任一建筑的灯光。即使灯光已经是开启状态，管理员仍可以按下开启按钮，或者在灯光关闭时按下关闭按钮，这些操作不会改变灯光的状态。

类似地，每条通道也有灯光系统，初始也是关闭状态。但与建筑灯光不同的是，通道的灯光会根据连接的建筑自动调整：如果管理员的操作后，连接的两座建筑灯光状态相同，则通道灯光会变为相同状态；如果不同，则通道灯光保持不变。

换句话说，如果管理员操作后，一条通道两端的建筑灯光都关闭，则通道灯光也会关闭；如果两端建筑灯光都开启，则通道灯光也会开启；如果一端开启而另一端关闭，则通道灯光状态保持不变。

在信息学奥林匹克竞赛参赛者到来前，校园主任对每个建筑和每条通道的灯光状态有明确的要求。

你需要求出管理员是否能通过一系列操作来实现主任的灯光要求。如果可能，找出任意一种操作序列。解决方案应正确识别是否可以达到所需的灯光状态，即使不提供具体的操作序列，也可以获得部分分数。

---

输入格式

输入包含多组数据。第一行包含一个整数 $t$ $(1 \leq t \leq 5 \cdot 10^4)$，表示测试数据的组数。

每组输入数据的第一行包含两个整数：$n, m$ $(1 \leq n \leq 10^5, 0 \leq m \leq 2 \cdot 10^5)$，分别表示建筑的数量和通道的数量。

接下来的 $m$ 行描述通道。每行包含三个整数 $a_i, b_i, c_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i , 0 \leq c_i \leq 1)$，分别表示连接的两个建筑的编号，以及通道 $i$ 的期望灯光状态。如果 $c_i=0$，则通道 $i$ 的灯光应该关闭；如果 $c_i=1$，则应该开启。

最后一行包含 $n$ 个整数 $d_1, d_2, \ldots , d_n$ $(0 \leq d_i \leq 1)$，表示每座建筑的期望灯光状态。如果 $d_v=0$，则建筑 $v$ 的灯光最终应该关闭；如果 $d_v=1$，则应该开启。

所有输入数据组的 $n$ 值之和不超过 $10^5$。所有输入数据组的 $m$ 值之和不超过 $2 \cdot 10^5$。

---

输出格式

对于每组输入数据：

• 如果无法通过一系列操作达到所需的灯光状态，输出 NO。
• 如果可能，输出 YES。如果不想展示具体的操作序列，接下来输出 -1 并继续到下一个输入数据组。如果想展示操作序列，则在下一行输出整数 $s$ $(0 \leq s \leq 10^6$，所有输入数据组的 $s$ 总和不应超过 $10^6)$，表示操作数，接着在下 $s$ 行输出具体操作。

对于每个操作 $i$，输出两个整数：$v_i, x_i$ $(1 \leq v_i \leq n, 0 \leq x_i \leq 1)$，分别表示进行操作的建筑编号和表示新的灯光状态，如果 $x_i=0$，则表示关闭建筑 $v_i$ 的灯光，如果 $x_i=1$，则表示开启。

---

样例

输入

5
4 4
1 2 0
2 3 1
3 4 0
2 4 1
0 1 0 0
4 4
1 2 0
2 3 1
3 4 0
4 1 1
0 1 0 1
1 0
1
1 0
0
2 1
1 2 0
0 0

输出

YES
5
4 1
3 1
2 1
3 0
4 0
NO
YES
1
1 1
YES
1
1 0
YES
0

在这个样例中，有五组测试数据。

• 在第一组数据中，包括四个用圆圈表示的建筑和四条用线条表示的连接。建筑或连接的灯光是否开启由粗线表示。需要五个步骤来实现所需的灯光效果。以下图像展示了灯光的初始状态和每个操作后的状态。

• 

• 在第二组数据中，需要实现四个建筑和四条连接的特定配置，但这是不可能的。

• 

• 在第三组数据中，有一个建筑需要开启灯光。这可以通过一个操作来完成。

• 在第四个数据中，有一个建筑，其灯光需要被关闭。可能的操作序列是在该建筑中进行单一的灯光关闭操作。这是一个合法的操作，尽管灯光已经是关闭状态。

• 在第五个数据中，有两个建筑和一个通道，所有的灯光都需要关闭。一个空的操作序列是合法的，可以实现这一配置。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	$N, n$ 的限制	$M, m$ 的限制	附加限制	子任务依赖
1	4	$n \leq 3$		$t \leq 230$
2	10	$N \leq 2000$	$M \leq 2000$	$n+m \leq 14$
3	8			$c_i=1$
4	6		$m=n-1, a_i=1, b_i=i+1$
5				$d_{a_i}=c_i, a_i<b_i$
6	8	$N \leq 2000$	$m=n-1, a_i=i, b_i=i+1$
7					6
8	10	$N \leq 2000$	$m=n-1$，任意两个建筑之间都联通
9	6				4, 6-8
10			$m=n, a_i=i, b_i=i \% n+1$
11	10	$N \leq 2000$	$M \leq 2000$		2, 6, 8
12	18				1，-11