유사 중위 순회

노드가 $N$개인 이진 트리가 있다. 이 트리를 중위 순회와 비슷한 방식으로 순회하려고 하며, 이를 유사 중위 순회라고 하자.

순회는 트리의 루트에서 시작하고, 중위 순회를 할 때 마지막으로 방문하는 노드에서 끝난다. 루트 노드는 항상 1번 노드이다.

유사 중위 순회는 루트 노드에서 시작해 다음 규칙에 따라 진행된다.

1. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
2. 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.
3. 그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
4. 그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
5. 유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.

위 그림에 있는 트리를 중위 순회하면 $4 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 6 \rightarrow 3 \rightarrow 7$ 순으로 방문한다.

따라서 유사 중위 순회의 끝은 노드 7이다.

유사 중위 순회는 위 그림과 같이 루트인 노드 $1$에서 시작해 노드 $7$에서 끝나며, $1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7$ 순서로 진행된다. 유사 중위 순회를 진행하면서 총 10번 이동하였다.

여기서 이동이란 하나의 노드에서 다른 노드로 한 번 움직이는 것을 뜻한다. 예를 들어 노드 1에서 노드 2로 가는 것은 한 번 이동한 것이다.

유사 중위 순회를 하면서 이동한 횟수를 구하려고 한다.

첫 번째 줄에 트리를 구성하는 노드의 개수 $N$이 주어진다.

두 번째 줄부터 $N + 1$ 번째 줄까지 현재 노드 $a$, 현재 노드의 왼쪽 자식 노드 $b$, 현재 노드의 오른쪽 자식 노드 $c$가 공백으로 구분되어 주어진다. 자식 노드의 번호가 -1인 경우 자식 노드가 없다는 것을 의미한다.

유사 중위 순회를 하면서 이동한 총 횟수를 출력한다.

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