你是“高效住宅”小区里一栋新建房屋的自豪业主。这个小区规划得非常高效，以至于没有任何冗余的街道，从高处看就像一棵树。传闻建造商将开始将房屋连接到排污网络。你已经知道了建造商遍历房屋的顺序。由于你希望自己的房子能尽快接通，你准备了一笔贿赂，以改变一小部分遍历顺序，使其对你有利。

给你一棵拥有 $N$ 个节点的树，根节点为 1。同时给你一个节点的编号 $K$（$1 \le K \le N$）。我们可以进行以下两种类型的树搜索：

• 从 1 开始进行 BFS，并在某个时刻切换为 DFS（可能立即在 1 处切换）。在搜索过程中，我们不一定非要切换到 DFS。
• 从 1 开始进行 DFS，并在某个时刻切换为 BFS（可能立即在 1 处切换）。在搜索过程中，我们不一定非要切换到 BFS。

在我们改变搜索类型（例如在节点 $z$ 处）之后，我们此后将只访问 $z$ 的子树中的节点。我们假设 $z$ 在第一次搜索中已经被访问过。

你必须针对这两种混合搜索，分别计算节点 $K$ 能够出现的最早位置（即第几个被访问，下标从 1 开始）。

在广度/深度优先搜索中，树中邻居节点的遍历顺序与输入中给出的顺序一致。你可以参考下面我们用于 DFS 和 BFS 的具体实现算法：

function traversal(adj_lists, type):
    p ← empty list {will contain the traversal nodes}
    waiting ← empty list {behaves as either a stack or a queue, depending on type}
    append (1, None) to waiting
    while waiting is not empty:
        (node, father) ← assign and pop rightmost if type = DFS else leftmost from waiting
        append node to p
        for each neigh in reversed(adj_lists[node]) if type = DFS else adj_lists[node]:
            {we need to reverse to enforce the input ordering for DFS}
            if neigh ≠ father:
                append (neigh, node) to waiting
    traversal(adj_lists, type ← DFS or BFS)

输入格式

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

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

如果 $Y$ 和 $Z$ 是 $X$ 的子节点，且在输入中边 $X-Y$（或 $Y-X$）出现在边 $X-Z$（或 $Z-X$）之前，那么在任何从包含 $X$ 的子树的节点开始的 DFS 或 BFS 中，$Y$ 都会在 $Z$ 之前出现。

输出格式

第一行输出如果以 BFS 开始，节点 $K$ 在混合搜索中可能被找到的最早位置（从 1 开始计数）。

第二行输出如果以 DFS 开始，对应的最早位置。

样例

输入样例 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

输出样例 1

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

输出样例 2

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

输出样例 3

9
9

说明

图 H.1：对于第一个样例，如果我们以 BFS 开始，在节点 3 切换到 DFS 是最优的，此时 $K = 13$ 是第 7 个被访问的节点。如果我们在节点 11 切换，则需要 11 个位置。如果我们以 DFS 开始，我们可以在节点 3 或节点 11 处进行最优切换。

图 H.2：对于第二个样例，如果我们以 DFS 开始，即使我们从未切换到 BFS，也有可能达到 7。

图 H.3：对于第三个样例，以哪种搜索开始并不重要，因为两种混合策略的最优答案都是 9。注意，如果我们只使用两种基本搜索之一，我们两次都会得到答案 10。