23734번 - Miswritten DFS 다국어

문제

Yunee is working on a data structures assignment. Yunee wrote a function DFS that traverses a binary tree in pre-order. However, Yunee's code recursively called DFS on the left subtree twice, by mistake.

function DFS(node v):
 visit v
 if v → left exists:
 DFS(v → left)
 DFS(v → left)
 if v → right exists:
 DFS(v → right)

The pseudocode of Yunee's DFS is as above. Now consider the following example.

If we pre-order traverse the above tree, the nodes 1,ドル 2, 3, 4, 5$ are visited in order. However, Yunee's DFS visits the nodes 1,ドル 2, 3, 3, 4, 2, 3, 3, 4, 5$ in order.

Given a binary tree, find the $K$-th node visited by Yunee's DFS. It is guaranteed that $K$ is not greater than the total number of visits. The nodes are numbered from 1ドル$ to $N$ and the root node is always node 1ドル$.

입력

The first line contains two integers $N$ and $K$ $(1\leq N \leq 10^5, 1\leq K \leq 10^{18})$. $N$ represents the number of nodes in the tree. $K$ is not greater than the total number of visits.

The next $N$ lines describe the tree. The $i$-th line contains two integers $l_i$ and $r_i$ $(0 \leq l_i, r_i \leq N)$. $l_i$ represents the left child of node $i$ and $r_i$ represents the right child of node $i$. If there is no corresponding child, 0ドル$ is given in place of $l_i$ or $r_i$.

The root node is always node 1ドル$.

출력

Output the $K$-th node visited by Yunee's DFS.

제한

힌트