쟤가 몸통입니다

문제 정보

문제

대한민국 최대의 불법 아르바이트 조직 albarden은 얼마 전까지만 해도 소문만 무성할 뿐, 실체가 없는 조직이었습니다. 그런데 며칠 전, albarden의 한 말단 조직원이 유명 해킹 사이트 todayspot에 댓글을 남기다 덜미가 잡혀, albarden의 조직도와 조직에 대한 몇 가지 정보가 유출되었습니다. 조직도에는 조직원 N명의 연결 관계가 트리 형태로 표현되어 있었고, 유출된 정보를 통해 이들 중 1명은 조직의 우두머리, M-1명은 조직의 몸통(중간 보스?)이라는 사실이 밝혀졌습니다. 또한 조직의 몸통들은 우두머리와 바로 연결되거나 다른 몸통들 만을 통해서 우두머리와 연결된다고 합니다. todayspot의 감 좋은 맴버 altertain은 N명 중 Q명의 우두머리 후보를 골라냈습니다. 각각의 우두머리 후보에 대해 가능한 몸통 맴버 구성의 가지 수를 계산하세요.

예를 들어 albarden의 조직도가 아래와 같고, 몸통이 2명일 때,

조직도

5번이 우두머리라면 몸통은 (1, 6)이나 (1, 2)로 구성될 수 있고, 가지 수는 2입니다. 1번이 우두머리라면 몸통은 (5, 6), (5, 2), (6, 2), (2, 3)으로 구성될 수 있고, 가지 수는 4입니다.

입력으로 서로 다른 조직원의 번호 A, B가 주어집니다. Q명의 우두머리 후보는 조직도에서 A와 B를 연결하는 경로의 Ki번째 조직원들로 구성됩니다. 예를 들어 위 그림에서 A = 6, B = 4, Q = 3이고 Ki가 각각 1 3 5라면, 각각 6, 2, 4번 조직원이 우두머리일 때의 가지 수를 세면 됩니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C가 주어집니다. 각 테스트 케이스의 첫 줄에는 조직원의 수 N, 우두머리와 몸통의 수 M, 그리고 조직원의 번호 A, B가 주어집니다. 그 후 N-1줄에 각각 연결된 두 조직원의 번호 Vi, Ui가 주어집니다. 그 다음 줄에는 우두머리 후보의 수 Q가 주어집니다. 그 다음 줄에는 Q명의 우두머리 후보를 나타내는 수 Ki가 주어집니다. Ki는 항상 조직도에서 A와 B를 연결하는 경로 상의 조직원 수 이하입니다. 조직원의 번호는 1부터 N까지의 자연수입니다. 한 조직원은 최대 5명의 조직원과 연결됩니다.

출력

각 테스트 케이스마다 한 줄에 Q명의 우두머리 후보에 대해 가능한 몸통 맴버 구성의 가지 수를 출력합니다. 답이 클 수 있으므로 답을 20130203으로 나눈 나머지를 출력합니다.

예제 입력

2
6 3 6 4
1 5
1 6
1 2
2 3
3 4
5
1 2 3 4 5
9 4 1 4
1 2
2 3
3 4
5 1
6 1
9 3
3 7
8 4
4
1 2 3 4

예제 출력

2 4 4 2 1 
6 10 12 7

노트

2 ≤ N ≤ 1000
2 ≤ M ≤ min(100, N)
1 ≤ A, B, Q, Ki ≤ N

5개의 댓글이 있습니다.