时间限制： 2.0 秒

空间限制： 512 MB

题目背景

让我们复习一下邓俊辉《数据结构》平衡二叉搜索树章节中的内容。

等价二叉树

若两棵二叉树的中序遍历序列相同，则称它们彼此等价；反之亦然。

zig 和 zag 旋转调整

最基本的修复手段，就是通过围绕特定节点的旋转，实现等价前提下的局部拓扑调整。

zig （右旋）操作如下图所示，设 c 和 Z 是 v 的左孩子、右 子树，X 和 Y 是 c 的左、右子树。所谓以 v 为轴的 zig 旋转，即如图(b)所示，重新调整这两个节点与三棵子树的联接关系：将 X 和 v 作为 c 的左子树、右孩子，Y 和 Z 分别作为 v 的左、右子树。

可见，尽管局部结构以及子树根均有变化，但中序遍历序列仍是 { ..., X, c, Y, v, Z, ... }，故 zig 旋转属于等价变换。

zag （左旋）操作如下图所示，设 X 和 c 是 v 的左子树、右孩子，Y 和 Z 分别是 c 的左、右子树。所谓以 v 为轴的 zag 旋转，即如图(b)所示，重新调整这两个节点与三棵子树的联接关系：将 v 和 Z 作为 c 的左孩子、右子树，X 和 Y 分别作为 v 的左、右子树。

同样地，旋转之后中序遍历序列依然不变，故 zag 旋转亦属等价变换。

题目描述

你现在有两棵有标号的、节点个数为 $n$ 的二叉树，你需要判断：是否能够通过至多 $2n$ 次 zig（右旋）/zag（左旋） 操作把初始状态变成目标状态。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$ 表示节点个数。

接下来 $n−1$ 行，每行 3 个数字 $x,y,c$，表示 $x$ 节点有孩子节点 $y$，如果 $c$ 为 0，则 $y$ 为左孩子，否则为右孩子。这棵树是初始状态。

再接下来 $n−1$ 行，每行 3 个数字 $x,y,c$，表示 $x$ 节点有孩子节点 $y$，如果 $c$ 为 0，则 $y$ 为左孩子，否则为右孩子。这棵树是目标状态。

保证输入的两棵树为合法的二叉树。

输出格式

输出到标准输出。

首先第一行输出 No 或 Yes，No 表示不能通过至多 $2n$ 次操作得到目标状态，否则输出 Yes。

如果输出 Yes，则接下来输出一行一个整数 $T$，表示你的构造方案中所用的操作次数。

接下来按操作顺序输出 $T$ 行，每行两个整数 $x,c$，如果 $c$ 为 0，则表示对节点 $x$ 做 zag（左旋）操作，否则做 zig（右旋）操作。

合法的构造方案不止一种，你只需要输出其中一种能正确抵达目标二叉树状态且旋转次数在 $2n$ 以内的方案即可。

3
3 1 0
1 2 1
1 3 1
3 2 0

Yes
3
1 0
2 1
3 1

样例 1 解释

转换过程如下图。

2
1 2 0
2 1 0

No

样例 2 解释

两者中序遍历不一致，无论如何都无法通过旋转操作到达。

子任务

对于所有数据，保证 $1\le n\le 10^6$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分数	$n\le$
1	30	$10$
2		$1000$
3	40	$10^6$

提示

邓俊辉《数据结构》习题 7-15

该习题的两小问分别解决了何时无解以及如何从二叉树转单链的问题，那么从二叉树转到另一个等价二叉树的过程还需要注意什么呢？

来源

清华大学 致理杯 202403