You are given a rooted Binary Tree, please print the last element that appears in the preorder traversal.
Note
- Each vertex of the tree is labeled 1 ~ n distinctly.
The first line is n: The number of vertices of the tree.
Then followed by n lines. Each line contains li , ri
li / ri denotes the left/right child of the i-th vertex.
If the vertex has no left/right child, the coresponding li / ri will be -1.
Restriction
- 1 <= n <= 106
Your output should be one line with one integer x.
x is the last element of the preorder traversal.