트리 합치기

컴퓨팅에서 트리는 위아래가 뒤집힌 그림으로 그린다. 루트가 맨 위에 있고 잎이 맨 아래에 있다. 트리는 $N$개의 정점이 $N-1$개의 간선으로 연결된 자료구조이고, 한 정점에서 간선을 따라가면 나머지 모든 정점에 도달한다. 루트가 있는 트리에서는 각 간선이 부모 정점과 자식 정점을 잇는다. 부모가 없는 정점이 딱 하나 있고, 이 정점을 루트라고 한다. 루트에서 출발해 부모에서 자식 방향으로 간선을 따라가면 트리의 나머지 모든 정점에 도달한다.

삼진 트리에서는 각 정점에 왼쪽, 가운데, 오른쪽이라고 부르는 자식이 최대 세 개까지 붙는다. 왼손 삼진 트리는 오른쪽 자식이 붙은 정점이 하나도 없는 삼진 트리이고, 오른손 삼진 트리는 왼쪽 자식이 붙은 정점이 하나도 없는 삼진 트리다. 삼진 트리의 루트는 언제나 가운데 정점이다. 아래 그림은 왼손 트리와 오른손 트리의 예다.

왼손 트리 $C$와 오른손 트리 $D$의 중첩 $S$는 다음 두 조건을 만족하는 삼진 트리다. 첫째, $S$의 루트는 $C$의 루트이거나 $D$의 루트이거나 두 루트를 겹쳐 놓은 정점이다. 둘째, $S$는 두 트리의 구조를 모두 담는다. 아래 그림은 위 그림의 왼손 트리와 오른손 트리를 중첩해서 만든 트리 몇 개다.

그림 (a)에서 루트는 오른손 트리의 정점 $x$이고, 정점 쌍 $(a, y)$와 $(c, u)$가 겹쳐져 있다. 그림 (b)에서 루트는 왼손 트리의 정점 $a$이고, 정점 쌍 $(d, x)$, $(e, y)$, $(f, u)$가 겹쳐져 있다. 그림 (c)에서도 루트는 왼손 트리의 정점 $a$이고, 정점 쌍 $(f, x)$가 겹쳐져 있다.

왼손 트리와 오른손 트리가 주어진다. 두 트리의 중첩인 삼진 트리를 만드는 데 필요한 정점의 최소 개수를 구하라.

첫째 줄에 왼손 트리의 정점 개수 $N$이 주어진다. 이 트리의 정점은 $1$번부터 $N$번까지의 번호로 구분하고, 루트는 $1$번 정점이다. 이어지는 $N$개의 줄에는 각각 세 정수 $I$, $L$, $K$가 주어진다. 정점 $I$의 왼쪽 자식이 $L$, 가운데 자식이 $K$라는 뜻이다.

그다음 줄에 오른손 트리의 정점 개수 $M$이 주어진다. 이 트리의 정점도 $1$번부터 $M$번까지의 번호로 구분하고, 루트는 $1$번 정점이다. 이어지는 $M$개의 줄에는 각각 세 정수 $P$, $Q$, $R$가 주어진다. 정점 $P$의 가운데 자식이 $Q$, 오른쪽 자식이 $R$라는 뜻이다.

값 $0$은 그 자리에 자식이 없다는 뜻이다. 정점을 설명하는 줄은 번호 순서대로 주어지지 않는다.

제약

• $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$

입력으로 주어진 두 트리의 중첩인 트리가 가질 수 있는 정점의 최소 개수를 한 줄에 출력한다.