Merging trees

In computing, trees are drawn upside down: the root sits at the top and the leaves sit at the bottom. A tree is a data structure of $N$ vertices connected by $N-1$ edges so that you can walk from any vertex to any other vertex along the edges. In a rooted tree, every edge joins a parent vertex to a child vertex. Exactly one vertex has no parent, and that vertex is the root. Starting at the root and following edges from parent to child, you reach every other vertex of the tree.

In a ternary tree, each vertex takes up to three children, called left, center, and right. A left-handed ternary tree is a rooted ternary tree in which no vertex has a right child. A right-handed ternary tree is a rooted ternary tree in which no vertex has a left child. The root of a ternary tree is always a center vertex. The figure below shows a left-handed tree and a right-handed tree.

A superposition $S$ of a left-handed tree $C$ and a right-handed tree $D$ is a ternary tree that meets two conditions. First, the root of $S$ is the root of $C$, or the root of $D$, or the two roots laid on top of each other. Second, $S$ contains the structure of both trees. The figure below shows a few trees built by superposing the left-handed tree and the right-handed tree above.

In figure (a) the root is vertex $x$ of the right-handed tree, and the vertex pairs $(a, y)$ and $(c, u)$ are superposed. In figure (b) the root is vertex $a$ of the left-handed tree, and the pairs $(d, x)$, $(e, y)$, $(f, u)$ are superposed. In figure (c) the root is again vertex $a$ of the left-handed tree, and the pair $(f, x)$ is superposed.

You are given a left-handed tree and a right-handed tree. Find the smallest number of vertices a ternary tree needs in order to be a superposition of the two given trees.

The first line contains an integer $N$, the number of vertices of the left-handed tree. Vertices of this tree are numbered from $1$ to $N$, and vertex $1$ is the root. Each of the next $N$ lines contains three integers $I$, $L$, $K$, meaning that the left child of vertex $I$ is $L$ and its center child is $K$.

The next line contains an integer $M$, the number of vertices of the right-handed tree. Vertices of this tree are numbered from $1$ to $M$, and vertex $1$ is the root. Each of the next $M$ lines contains three integers $P$, $Q$, $R$, meaning that the center child of vertex $P$ is $Q$ and its right child is $R$.

The value $0$ means that the child in that slot does not exist. The lines describing vertices do not arrive in numerical order.

Constraints

• $1 \le N \le 10^4$
• $0 \le I, L, K \le N$
• $1 \le M \le 10^4$
• $0 \le P, Q, R \le M$

Print, on one line, the smallest number of vertices of a tree that is a superposition of the two trees given in the input.