잘못 작성된 DFS

Yunee는 자료구조 과제를 하고 있다. Yunee는 이진 트리를 전위 순회하는 함수 DFS를 작성했다. 그런데 실수로 왼쪽 부분 트리에 DFS를 두 번 재귀 호출하는 코드를 작성하고 말았다.

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

Yunee의 DFS 의사 코드는 위와 같다. 이제 다음 예시를 보자.

위 트리를 전위 순회하면 노드 $1, 2, 3, 4, 5$가 순서대로 방문된다. 그러나 Yunee의 DFS는 노드 $1, 2, 3, 3, 4, 2, 3, 3, 4, 5$를 순서대로 방문한다.

이진 트리가 주어졌을 때, Yunee의 DFS가 방문하는 $K$번째 노드를 구하시오. $K$는 전체 방문 횟수보다 크지 않음이 보장된다. 노드는 $1$부터 $N$까지 번호가 붙어 있고, 루트 노드는 항상 $1$번 노드이다.

첫 번째 줄에 두 정수 $N$과 $K$가 주어진다. $(1\leq N \leq 10^5, 1\leq K \leq 10^{18})$ $N$은 트리의 노드 수를 나타낸다. $K$는 전체 방문 횟수보다 크지 않다.

다음 $N$개의 줄은 트리를 나타낸다. $i$번째 줄에 두 정수 $l\_i$와 $r\_i$가 주어진다. $(0 \leq l\_i, r\_i \leq N)$ $l\_i$는 노드 $i$의 왼쪽 자식, $r\_i$는 노드 $i$의 오른쪽 자식을 나타낸다. 해당하는 자식이 없으면 $l\_i$ 또는 $r\_i$ 대신 $0$이 주어진다.

루트 노드는 항상 $1$번 노드이다.

Yunee의 DFS가 방문하는 $K$번째 노드를 출력한다.