给一个有根二叉树,可以无限次的交换任意节点的左右子树,问最少交换多少次使得该树的中序遍历的字典序最小?
输入描述:
每个测试点有仅有一组数据
每组测试数据的一行有两个整数N,M,代表有N个节点,M为根节点。
接下来N行,每行两个整数ai,bi.ai表示第i个节点的左儿子,bi表示第i个节点的右儿子.
N∈[1,5×105]
ai,bi,M∈[1,N] 当ai,bi为0时 表示空节点.
输出描述:
输出两行
第一行 为最小交换次数.
第二行 为字典序最小的中序遍历.
示例1
输入
复制
7 4
0 0
1 3
0 0
2 5
6 7
0 0
0 0