Marbles on the tree

A binary tree is a tree in which every node has at most two children. The number drawn inside each node of the picture is the node number.

The binary tree in this problem is rooted at node 1, and the order of the children matters. You cannot swap the left side and the right side of any subtree.

Put one marble on the root. The marble falls by the following process.

1. If the node holding the marble has no child, the marble stops there.
2. If the node has exactly one child, the marble falls to that child.
3. If the node has two children, the marble falls to the left child when the number of marbles already resting in the left subtree is less than or equal to the number of marbles already resting in the right subtree, and to the right child otherwise.
4. Repeat the process until the marble stops.

Every marble ends up on a leaf. Marbles are dropped one at a time, and the next marble is put on the root only after the previous one has stopped.

Dropping marbles on the tree in the picture, the first five stop on nodes 2, 4, 2, 5, 2 in that order.

When the tree is small or the marbles are few, plain simulation tells you where each marble stops. The answer has to come out quickly for a large tree with a huge number of marbles as well.

Given a binary tree and $K$, find the number of the node where the $K$-th marble stops.

The first line contains the number of nodes $N$ of the binary tree. ($1 \le N \le 200000$)

Each of the next $N$ lines contains two integers $U$ and $V$. On the $i$-th of these lines, $U$ is the left child of node $i$ and $V$ is the right child of node $i$. If $U$ is $-1$, node $i$ has no left child. If $V$ is $-1$, node $i$ has no right child. A value other than $-1$ always satisfies $2 \le U, V \le N$.

The last line contains $K$. ($1 \le K \le 10^{18}$)

The given tree is always a valid binary tree, and the root is node 1.

Print the number of the node where the $K$-th marble stops.