/ tabris / 题库 /

tabris is SirBat 1 (**数据范围有改动**) 在这个oj后三组数据会栈溢出 最好手工栈

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

信息

难度
9
分类
(无)
标签
(无)
递交数
13
已通过
1
通过率
8%
上传者