题目描述

你刚刚在“高效住宅区”买下了一栋新房。这个住宅区的道路没有任何冗余，从空中看起来恰好是一棵树。

据说施工方即将依次为各栋房屋接入污水管网。你知道施工人员访问房屋的顺序。为了让自己的房屋尽早接通，你打算行贿，让施工人员稍微修改搜索方式。

给定一棵以结点 $1$ 为根、共有 $N$ 个结点的树，以及一个目标结点 $K$。施工人员可以使用下列两种混合搜索方式之一：

1. 从结点 $1$ 开始进行 BFS，并在某个时刻切换为 DFS。可以在结点 $1$ 处立即切换，也可以始终不切换；
2. 从结点 $1$ 开始进行 DFS，并在某个时刻切换为 BFS。可以在结点 $1$ 处立即切换，也可以始终不切换。

假设在结点 $z$ 处切换搜索方式。结点 $z$ 已经由第一种搜索访问；切换之后，只继续访问以 $z$ 为根的子树中的结点，第一阶段尚未访问的其他结点全部忽略。

对于上述两种混合搜索，分别求目标结点 $K$ 最早可能出现在访问序列中的位置。

树中相邻结点的处理顺序由边在输入中的出现顺序确定。题目采用的 DFS 和 BFS 精确定义如下。

function traversal(adj_lists, type):
    p <- 空列表
    waiting <- 空列表
    将 (1, None) 加入 waiting

    while waiting 非空:
        if type = DFS:
            从 waiting 的右端取出 (node, father)
        else:
            从 waiting 的左端取出 (node, father)

        将 node 加入 p

        if type = DFS:
            按 adj_lists[node] 的逆序枚举 neigh
        else:
            按 adj_lists[node] 的原顺序枚举 neigh

        对每个 neigh:
            if neigh != father:
                将 (neigh, node) 加入 waiting

DFS 中逆序压入相邻结点，是为了保证实际访问顺序仍与输入顺序一致。

输入格式

第一行包含两个整数 $N,K$（$1\le N\le 10^5$）。

接下来 $N-1$ 行，每行包含两个整数 $A,B$（$1\le A,B\le N$），表示结点 $A$ 与结点 $B$ 之间有一条边。

若 $Y$ 和 $Z$ 都是 $X$ 的孩子，并且边 $XY$（或 $YX$）在输入中先于边 $XZ$（或 $ZX$）出现，那么在任何包含 $X$ 的子树上进行 DFS 或 BFS 时，$Y$ 都会先于 $Z$ 被访问。

输出格式

第一行输出：从 BFS 开始、至多切换一次为 DFS 时，结点 $K$ 能够出现的最小位置。位置从 $1$ 开始编号。

第二行输出：从 DFS 开始、至多切换一次为 BFS 时，结点 $K$ 能够出现的最小位置。

样例说明

样例 1 的最优切换方式

对于样例 1：

• 从 BFS 开始时，最优方案是在结点 $3$ 处切换为 DFS，此时 $K=13$ 是第 $7$ 个访问的结点；
• 若改在结点 $11$ 处切换，则需要到第 $11$ 个位置才访问到 $K$；
• 从 DFS 开始时，可以在结点 $3$ 或结点 $11$ 处切换，并得到最优结果。

样例 2 的最优切换方式

对于样例 2，从 DFS 开始时，即使始终不切换为 BFS，也可以使目标结点出现在第 $7$ 个位置。

样例 3 的最优切换方式

对于样例 3，无论从哪一种搜索开始，最优答案都是 $9$。若只使用纯 BFS 或纯 DFS，则两种情况下目标结点都只能出现在第 $10$ 个位置。

样例 1

输入

16 13
1 2
1 3
1 4
1 5
2 6
2 7
3 11
4 15
4 16
7 8
7 9
11 12
11 13
9 10
12 14

输出

7
11

样例 2

输入

15 10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

输出

6
7

样例 3

输入

11 10
1 2
1 3
3 4
4 5
4 6
5 7
7 8
6 9
6 10
1 11

输出

9
9