나무 위의 구슬

이진 트리는 모든 노드의 자식이 2개 이하인 트리이다. 그림의 각 노드에 적힌 수는 노드 번호이다.

이 문제에서 다루는 이진 트리는 루트가 1번 노드로 고정되어 있고, 자식의 순서가 중요하다. 어떤 서브트리에서도 왼쪽과 오른쪽을 바꿀 수 없다.

루트에 구슬을 하나 올려놓으면 구슬은 다음 과정을 거쳐 떨어진다.

1. 구슬이 놓인 노드에 자식이 없으면 그 자리에서 멈춘다.
2. 자식이 하나뿐이면 그 자식으로 떨어진다.
3. 자식이 둘이면, 왼쪽 서브트리에 쌓인 구슬의 수가 오른쪽 서브트리에 쌓인 구슬의 수보다 작거나 같을 때 왼쪽 자식으로 떨어지고, 그 외에는 오른쪽 자식으로 떨어진다.
4. 구슬이 멈출 때까지 위 과정을 되풀이한다.

구슬은 결국 단말 노드에 쌓인다. 구슬은 한 번에 하나씩 떨어뜨리며, 앞의 구슬이 멈춘 뒤에 다음 구슬을 루트에 올려놓는다.

그림과 같은 트리에 구슬을 차례로 떨어뜨리면 첫 다섯 개의 구슬은 2번, 4번, 2번, 5번, 2번 노드에서 멈춘다.

트리가 작거나 구슬이 적으면 직접 시뮬레이션해서 멈추는 자리를 알아낼 수 있다. 큰 트리에 구슬을 아주 많이 떨어뜨리는 경우에도 빠르게 답을 구해야 한다.

이진 트리와 $K$가 주어질 때, $K$번째 구슬이 멈추는 노드의 번호를 구하라.

첫 줄에 이진 트리의 노드 수 $N$이 주어진다. ($1 \le N \le 200000$)

다음 $N$개의 줄 중 $i$번째 줄에는 두 정수 $U$와 $V$가 주어진다. $U$는 $i$번 노드의 왼쪽 자식이고 $V$는 $i$번 노드의 오른쪽 자식이다. $U$가 $-1$이면 왼쪽 자식이 없고, $V$가 $-1$이면 오른쪽 자식이 없다. $-1$이 아닌 값은 항상 $2 \le U, V \le N$을 만족한다.

마지막 줄에 $K$가 주어진다. ($1 \le K \le 10^{18}$)

주어지는 트리는 항상 올바른 이진 트리이며, 루트는 1번 노드이다.

$K$번째 구슬이 멈추는 노드의 번호를 출력한다.