URI Online Judge | 2240

Merging Trees

By Maratona de Programação da SBC – 2016 BR Brazil

Timelimit: 1

Computing trees are foreign objects: the root is at the top and the leaves are down! A tree is a data structure comprised of N vertices connected by edges N-1 so that it is possible to reach an apex at any other vertex following the edges. In a rooted tree, each edge connects a vertex parent to a child vertex. A single vertex has no father, and is called the root. Thus, from the root it is possible to reach any other vertex of the tree following the edges in the direction of father to son.

In a ternary tree each node can have up to three children vertices, called the left, center and right. Handed a ternary tree is a rooted ternary tree in which no vertex has right child. A right hand ternary tree is a rooted ternary tree in which no vertex has left child. The root of a ternary tree is always a central apex. The figure below shows examples of a left-handed tree and a right hand tree.

tree

The superposition S of a left-handed tree C with a right-hand tree D is a rooted ternary tree in which the root is either the root of C or the root of D or both roots, C and D, superimposed, and which contains the Structure of both superimposed trees. The figure below shows some trees formed by the superposition of the left-handed tree and the right tree of the figure above.

tree

Note that in Figure (a) is the root vertex x (the right hand tree) and the pairs of vertices (a, y) and (c, u) are superposed. In Figure (b) is the root vertex (the left-handed tree) and the pairs of vertices (d, x), (e, y) and (f u) are superposed. In Figure (c) it is also the root vertex (the left-handed tree) and the pair of vertices (f, x) is superimposed.

Given a left-handed tree and a tree right hand, your task is to determine the minimum number of vertices needed to build a ternary tree which is a superposition of the given trees.

Input

The first line of a test case contains an integer N indicating the number of vertices of the left-handed tree (1 ≤ N ≤ 104). Vertices in this tree are identified by numbers from 1 to N, and the root is the number of vertex 1. Each of the following N lines contains three integers I, L and K, respectively, indicating a vertex I identifier, the left L child identifier I and the central child identifier K of I (0 ≤ I, L, KN). The next line contains an integer M indicating the number of vertices of the right hand tree (1 ≤ M ≤ 104).Vertices in this tree are identified by numbers from 1 to M, and the root is the number of vertex 1. Each of the next M lines contains three integers P, Q and R, respectively indicating the identifier of a vertex P, the son of the identifier central Q of P and the son of the right identifier R of P (0 ≤ P, Q, RN). The value zero indicates a non-existing vertex (a vertex is used when no one or both of its children).

Output

Print the minimum number of vertices of a tree that is the superposition of the two trees given at the entrance.

Input Samples Output Samples

7
1 2 3
2 0 0
3 4 0
4 0 5
5 0 6
6 7 0
7 0 0
7
1 2 3
2 4 0
3 5 0
4 0 6
5 0 0
6 0 7
7 0 0

11

5
1 2 3
2 4 5
3 0 0
4 0 0
5 0 0
3
1 2 3
2 0 0
3 0 0

6

3

3 0 2

2 0 0

1 0 3

2

2 0 0

1 2 0

3