题目思路

思维题。

将所有节点尝试都转化为全奇或者全偶

转化为全奇时，我们只需要从根节点开始遍历一遍树，在回溯时，如果子节点不是奇数，那么就操作该条边一次，将子节点变成奇数。最终，如果能够满足奇偶相同，那么根节点一定是奇数，否则就不能满足。 转化为全偶时同理

代码

题目描述

小红想将一棵树的所有结点的值变成奇偶相同。但是，他每次只能选择两个相邻节点使它们的值同时增加1。小红想知道，他能做到吗？

小红有$q$棵树。

输入描述

第一行输入$q$

接下来输入每棵树。

第一行输入$n$，代表这棵树总共有$n$个节点。

第二行为$a_i$，代表每个节点的初始值。

接下来$n-1$行，每行为$u,v$，代表节点$u$和$v$间存在一条边。

$1\le n \le 10^5$

$1\le a_i \le 10^9$

$1\le u,v \le n$

所有树的节点个数和不超过200000。

输出描述

对于每棵树，第一行输入"Yes"代表可以，否则输出"No"

接下来输出一个数字$p$，代表总共操作的次数，接下来$p$行，输出你的操作。

不需要最小化操作次数，但是需要保证操作次数不超过$n$

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

2
4
1 2 2 3
1 2
2 3
3 4
4
1 2 3 3
1 2
2 3
2 4

输出

Yes
3
1 2
2 3
3 4
No