tabris is SirBat 1 (**数据范围有改动**) 在这个oj后三组数据会栈溢出 最好手工栈
Background
Special for beginners, ^_^
Description
给一个有根二叉树,可以无限次的交换任意节点的左右子树,问最少交换多少次使得该树的中序遍历的字典序最小?
Format
Input
每个测试点有仅有一组数据
每组测试数据的一行有两个整数N,M,代表有N个节点,M为根节点。
接下来N行,每行两个整数\(a_i,b_i\).\(a_i\)表示第i个节点的左儿子,\(b_i\)表示第i个节点的右儿子.
\(N\in[1,5\times 10^5]\)
\(a_i,b_i,M\in[1,N]\) 当\(a_i,b_i\)为0时 表示空节点.
Output
输出两行
第一行 为最小交换次数.
第二行 为字典序最小的中序遍历.
Sample 1
Input
7 4
0 0
1 3
0 0
2 5
6 7
0 0
0 0
Output
0
1 2 3 4 5 6 7
Limitation
1s, 1024KiB for each test case.
Hint
/***
Input
3
7 4
0 0
1 3
0 0
2 5
6 7
0 0
0 0
7 4
5 7
6 3
0 0
2 1
0 0
0 0
0 0
7 4
0 0
6 3
0 0
2 5
1 7
0 0
0 0
Output
0
1 2 3 4 6 5 7
1
3 2 6 4 5 1 7
2
1 5 7 4 3 2 6
***/
Source
tabris
