트리 유사도

숫자가 적혀 있는 순서 있는 루트 트리(labeled ordered rooted tree) 두 개 $T$와 $T'$가 주어진다. 두 트리 사이의 거리를 구하는 프로그램을 작성하시오. 거리란 $T$를 $T'$와 동등하게 만드는 데 필요한 최소 연산 횟수이다.

연산은 다음 세 가지이다.

1. $T$의 한 노드에 적힌 숫자를 다른 숫자로 바꾼다.
2. $T$에서 루트가 아닌 노드 하나를 삭제한다.
3. $T$의 루트 아래 어딘가에 노드 하나를 삽입한다.

$T$와 $T'$는 순서 있는 트리이므로, 리프가 아닌 노드가 자식을 $c$개 가지면 그 자식들에는 1번째부터 $c$번째까지 순서가 정해져 있다.

두 트리 $X$와 $Y$가 동등하려면, 두 루트에 같은 숫자가 적혀 있고 자식의 개수가 같아야 하며, 각 $i$에 대해 $X$의 $i$번째 자식을 루트로 하는 서브트리와 $Y$의 $i$번째 자식을 루트로 하는 서브트리가 서로 동등해야 한다. ($i = 1, 2, \dots, c$)

삭제와 삽입은 다음과 같이 정의된다. 루트가 아닌 노드 $w$가 자식을 $d$개 가지고, $w$의 부모가 $u$이며 $w$가 $u$의 $i$번째 자식이라고 하자. $w$를 삭제하면 $w$의 자식들이 $w$가 있던 자리로 올라온다. 즉 $w$의 첫 번째 자식이 $u$의 $i$번째 자식이 되고, 두 번째 자식이 $u$의 $(i+1)$번째 자식이 되는 식이다. $u$의 자식 중 $j < i$인 $j$번째 자식은 순서가 그대로 유지되고, $j > i$인 $j$번째 자식은 모두 $u$의 $(j + d - 1)$번째 자식으로 밀려난다.

루트가 아닌 노드 $w$를 삽입하려면 먼저 $w$의 부모가 될 노드 $u$를 고른다. 그런 다음 $u$의 자식 중에서 연속한 부분 수열을 골라 $w$의 자식으로 만들고, 그 자리에 $w$를 끼워 넣는다. 삽입할 때 $w$에는 원하는 숫자를 적을 수 있다.

$T$의 루트를 삭제하거나 루트 위에 새 노드를 삽입하는 것은 불가능하다. 단, 루트에 적힌 숫자는 바꿀 수 있다.

(예를 들어, 노드 $w$를 삭제하는 연산과, $u$의 2번째 자식부터 4번째 자식까지를 새 노드 $w$의 자식으로 묶어 $u$ 아래에 $w$를 삽입하는 연산을 생각할 수 있다.)

첫째 줄에 두 트리 $T$와 $T'$의 노드 개수 $n$, $m$이 주어진다. ($1 \le n, m \le 60$)

이어지는 $n$개의 줄에는 $T$의 정보가 주어진다. 노드는 $0$번부터 $n-1$번까지 번호가 매겨지며, 이 $n$개 줄 중 $(i+1)$번째 줄에 노드 $i$의 정보가 주어진다. 각 줄에는 그 노드에 적힌 숫자와 자식의 수가 주어지고, 이어서 자식 노드의 번호가 순서대로 주어진다(번호는 $0$부터 시작한다).

그다음 $m$개의 줄에는 같은 형식으로 $T'$의 정보가 주어진다.

노드에 적힌 숫자는 항상 음이 아닌 정수이며, 각 트리의 루트는 다른 어떤 노드의 자식도 아닌 노드이다.

$T$를 $T'$와 동등하게 만드는 데 필요한 최소 연산 횟수를 출력한다.