시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Em Computação árvores são objetos estranhos: a raiz está no topo e as folhas estão embaixo! Uma árvore é uma estrutura de dados composta de N vértices conectados por N-1 arestas de forma que é possível chegar de um vértice a qualquer outro vértice seguindo as arestas. Em uma árvore enraizada, cada aresta conecta um vértice pai a um vértice filho. Um único vértice não tem pai, e é chamado de raiz. Assim, partir da raiz é possivel chegar a qualquer outro vértice da árvore seguindo as arestas na direção de pai para filho.

Em uma árvore ternária cada vértice pode ter até três vértices filhos, chamados esquerdo, central e direito. Uma árvore ternária canhota é uma árvore ternária enraizada em que nenhum vértice tem filho direito. Uma árvore ternária destra é uma árvore ternária enraizada em que nenhum vértice tem filho esquerdo. A raiz de uma árvore ternária é sempre um vértice central. A figura abaixo mostra exemplos de uma árvore canhota e de uma árvore destra.

A superposição S de uma árvore canhota C com uma árvore destra D é uma árvore ternária enraizada em que a raiz é ou a raiz de C ou a raiz de D ou ambas as raízes, de C e de D, superpostas, e que contém a estrutura de ambas as árvores superpostas. A figura abaixo mostra algumas árvores formadas pela superposição da árvore canhota e da árvore destra da figura acima.

Note que na Figura (a) a raiz é o vértice x (da árvore destra) e os pares de vértices (a, y) e (c, u) são superpostos. Na Figura (b) a raiz é o vértice a (da árvore canhota) e os pares de vértices (d, x), (e, y) e (f, u) são superpostos. Na Figura (c) a raiz também é o vértice a (da árvore canhota) e o par de vértices (f, x) é superposto.

Dadas uma árvore canhota e uma árvore destra, sua tarefa é determinar o número mínimo de vértices necessários para construir uma árvore ternária que é uma superposição das árvores dadas.

입력

A primeira linha de um caso de teste contém um inteiro N indicando o número de vértices da árvore canhota. Vértices nesta árvore são identificados por números de 1 a N, e a raiz é o vértice de número 1. Cada uma das N linhas seguintes contém três inteiros I, L e K, indicando respectivamente o identificador de um vértice I, o identificador do filho esquerdo L de I e o identificador do filho central K de I. A linha seguinte contém um inteiro M indicando o número de vértices da árvore destra. Vértices nesta árvore são identificados por números de 1 a M, e a raiz é o vértice de número 1. Cada uma das M linhas seguintes contém três inteiros P, Q e R, indicando respectivamente o identificador de um vértice P, o identificador do filho central Q de P e o identificador do filho direito R de P. O valor zero indica um vértice não existente (usado quando um vértice não tem um ou ambos os seus filhos).

Restrições

  • 1 ≤ N ≤ 104
  • 0 ≤ I,L,K ≤ N
  • 1 ≤ M ≤ 104
  • 0 ≤ P,Q,R ≤ N

출력

Imprima o número mínimo de vértices de uma árvore que é a superposição das duas árvores dadas na entrada.

 

예제 입력 1

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

예제 출력 1

11

예제 입력 2

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

예제 출력 2

6

예제 입력 3

3
3 0 2
2 0 0
1 0 3
2
2 0 0
1 2 0

예제 출력 3

3