내년에 회사를 퇴직하는 김 부장은 퇴직 후 커피전문점을 차리려고 계획하고 있다. 김 부장이 사는 지역의 도로망은 아래 그림과 같이 트리 형태로 구성되어 있다. 원으로 표시된 부분은 커피전문점 설치 후보지이고, 선은 도로를 나타낸다. 인접한 후보지 사이의 도로 길이는 모두 동일하다고 가정한다. 이 지역에는 대규모 아파트 단지가 세 군데 있다. 아파트의 위치는 그림에서 A, B, C로 표시된 곳이다.

김 부장은 커피전문점 후보지 중에서 다음의 조건을 만족하는 장소를 최적지라고 생각한다.

최적지 p는 다른 모든 후보지 q와 비교할 때, 아파트 단지 A, B, C 중에 적어도 한 곳과는 더 가까워야 한다. 즉, d(x, y)를 x와 y 사이의 거리라고 할 때, 최적지 p는 다른 모든 후보지 q에 대해 d(p,A) < d(q,A) 또는 d(p,B) < d(q,B) 또는 d(p,C) < d(q,C) 이어야 한다.

위 그림에서 커피전문점 최적지는 1, 2, 3, 5, 6, 8이다. 후보지 7은 후보지 6과 비교할 때 아파트 단지 A, B, C의 어떤 한 곳도 더 가까이 있지 않기 때문에 최적지가 될 수 없다.

김 부장은 커피전문점 최적지의 개수를 알기를 원한다. 또한 주어진 어떤 후보지가 최적지인지 알고 싶다. 만일 최적지가 아니라면 그 후보지에 가장 가까운 최적지를 알기를 원한다. 그림에서 후보지 9에 가장 가까운 최적지는 6이고, 후보지 4에 가장 가까운 최적지는 3이다. 김 부장을 도울 수 있는 프로그램을 작성하시오.

1. 첫째 줄에 트리의 노드(후보지)의 개수를 나타내는 정수 n이 주어진다. (2≤n≤100,000) 후보지는 1부터 n까지의 번호로 구분된다.
2. 둘째 줄부터 n-1개의 줄에 각 줄마다 후보지 쌍을 나타내는 두 개의 정수 p, q가 주어진다, 이것은 후보지 p와 q 사이에 도로가 존재함을 의미한다.
3. 그 다음 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수 A, B, C가 주어진다, A, B, C는 후보지 번호 중의 하나이다. (A≠B, A≠C, B≠C)
4. 그 다음 줄에는 질의에 해당하는 후보지의 개수 m이 주어진다. (1≤m≤20,000)
5. 그 다음 m개의 줄에는 각 줄마다 후보지 번호가 주어진다.

1. 첫 줄에 커피전문점 최적지의 개수를 출력한다.
2. 둘째 줄부터 m개의 줄에 걸쳐 각 줄마다 각 질의에 해당하는 후보지에 가장 가까운 최적지 번호를 출력한다. 만일 주어진 후보지가 바로 최적지이면 해당 후보지 번호를 그대로 출력한다.

교원프로그래밍 2010