Similar Inorder Traversal

There is a binary tree with $N$ nodes. We want to traverse the tree in a way similar to inorder traversal. Call this a similar inorder traversal.

The traversal starts at the root of the tree and ends at the node that would be visited last in an inorder traversal. The root node is always node 1.

A similar inorder traversal starts at the root node and proceeds as follows.

1. If the current node has a left child that has not been visited yet, move to the left child.
2. Otherwise, if the current node has a right child that has not been visited yet, move to the right child.
3. Otherwise, if the current node is the end of the similar inorder traversal, terminate the similar inorder traversal.
4. Otherwise, if the current node has a parent, move to the parent.
5. Repeat steps 1 to 4 until the similar inorder traversal terminates.

An inorder traversal of the tree in the figure visits the nodes in the order $4 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 6 \rightarrow 3 \rightarrow 7$.

Therefore, the end of the similar inorder traversal is node 7.

As shown in the figure, the similar inorder traversal starts at the root node $1$, ends at node $7$, and proceeds in the order $1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7$. While performing the similar inorder traversal, it made 10 moves in total.

Here, a move means going from one node to another node once. For example, going from node 1 to node 2 is one move.

We want to find the number of moves made during a similar inorder traversal.

The first line gives the number of nodes in the tree, $N$.

Lines 2 to $N + 1$ each give the current node $a$, its left child $b$, and its right child $c$, separated by spaces. A child number of -1 means there is no such child.

Print the total number of moves made during the similar inorder traversal.

• $1 \le N \le 100,000$
• $1 \le a, b \le N$