경비원

어떤 왕국의 왕은 왕국의 위대함을 널리 알리기 위해 거대한 성을 지으려 한다. 성은 여러 개의 빌딩이 서로 연결된 형태이며, 각 빌딩은 여러 개의 홀과 그 홀들을 잇는 복도로 이루어져 있다.

처음에 성은 빌딩 하나로만 이루어져 있고, 이 빌딩을 메인 빌딩이라고 부른다. 왕국의 인구가 늘어날 때마다 성은 다음과 같이 확장된다. 새로운 부속 빌딩이 지어지면 그 빌딩은 이미 존재하던 빌딩 하나와 연결된다. 새 빌딩도 다른 빌딩과 마찬가지로 홀과 복도로 이루어진다. 이때 기존 빌딩의 어떤 홀과 새 빌딩의 어떤 홀을 잇는 새로운 복도를 하나 놓는데, 이 복도는 새 빌딩으로 통하는 유일한 통로이다.

한 빌딩에 있을 수 있는 홀의 최대 개수는 $10$개이다. 이렇게 만들어진 빌딩들의 연결 관계는 트리 구조를 이룬다.

왕은 모든 홀에 전략적으로 경비원을 배치하여 성의 모든 복도를 감시하려고 한다. 경비원은 자신이 서 있는 홀에 연결된 모든 복도를 감시할 수 있으므로, 어떤 복도든 그 복도가 잇는 두 홀 중 적어도 한 곳에 경비원이 있으면 그 복도는 감시된다. 왕은 개인 경호에 인력을 최대한 남겨 두고 싶어 하므로, 성의 모든 복도(빌딩 내부의 복도와 빌딩 사이를 잇는 복도 모두)를 감시하는 데 필요한 경비원의 수를 최소로 하려고 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 성은 재귀적으로 정의되며, 메인 빌딩부터 주어진다. 모든 홀은 $1$ 이상 $10000$ 이하의 정수로 구별되고, 한 성 안에서 홀 번호는 서로 다르다.

하나의 빌딩에 대한 정보는 다음과 같이 주어진다. 첫 줄에 그 빌딩을 이루는 홀의 수 $n$ ($2 \le n \le 10$), 빌딩 내부 복도의 수 $m$ ($1 \le m \le 45$), 그리고 이 빌딩에 직접 연결된 부속 빌딩의 수 $w$ ($0 \le w \le 10$)가 주어진다.

이어서 $m$개의 줄에 걸쳐 이 빌딩 내부 복도의 정보가 주어진다. 각 줄에는 그 복도가 잇는 두 홀의 번호가 주어지며, 두 홀은 항상 같은 빌딩 안에 있다.

그 다음 $w$개의 부속 빌딩에 대한 정보가 차례로 주어진다. 각 부속 빌딩마다 먼저 한 줄에 두 정수가 주어지는데, 이는 현재 빌딩의 홀 번호와 그 부속 빌딩의 홀 번호로, 두 빌딩을 잇는 복도를 나타낸다. 그 줄 바로 다음에 해당 부속 빌딩의 정보가 메인 빌딩과 같은 형식으로 재귀적으로 주어진다.

성은 항상 전체가 연결되어 있다. 즉, 임의의 두 홀은 직접 또는 다른 홀을 거쳐 연결되어 있다. 같은 두 홀을 잇는 복도는 최대 한 개만 존재한다. 입력은 파일의 끝까지 계속되며, 각 테스트 케이스는 하나의 완전한 성을 나타낸다.

각 테스트 케이스마다 성의 모든 복도를 감시하는 데 필요한 경비원 수의 최솟값을 한 줄에 하나씩 출력한다.