Informatica Online Judge

  Network [0675 / 02A3]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 4   Total Tried : 11


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

승현이는 NIA에 도착해서야 자신이 들고 온 물건이 스마트폰밖에 없다는 것을 깨닫습니다. 하지만 상에 대한 분노로 경비원 몰래 NIA 서버실에 침입하여 서버 지도 및 연결 방법을 스마트폰에 담아 오는 것을 성공했습니다.

NIA의 서버는 승현이의 생각 외로 매우 단순했습니다. NIA에는 N개의 서버가 있고, 이 서버들은 1부터 N까지의 번호가 붙어 있으며, N-1개의 케이블로 서로 연결되어 있습니다. 또한 서로 다른 두 서버끼리 통신할 방법이 무조건 있다고 합니다. 이러한 단순한 서버 구조에 신난 승현이는 아래와 같은 방법으로 NIA 서버 전체를 마비시키려고 합니다.

임의의 서버 하나를 정해 이 서버로 트래픽을 보내 그 서버를 마비시킵니다. 하나의 서버를 마비시키면, 그 서버와 연결된 케이블들은 무용지물이 됩니다. 이 과정을 반복합니다.
NIA 서버 전체를 마비시킨다는 것은 NIA의 어떠한 서버끼리도 케이블을 통해 서로 통신할 수 없다는 것을 의미합니다.
단, NIA에서 정해 놓은 K개의 서버들을 마비시키면 서버 관리자가 경고를 받고 승현이의 공격을 방어할 수 있기 때문에, 이 서버들은 마비시킬 수 없습니다.
하나의 서버를 마비시키기 위해서는 많은 트래픽을 보내야 하기 때문에 서버를 마비시키는 동안에는 승현이가 게임을 할 수가 없습니다. 게임을 너무 하고 싶은 승현이는 최소한의 서버를 공격하여 NIA 서버 전체를 마비시키려고 합니다.

이 때, 승현이가 공격해야 할 최소한의 서버 수를 구하는 프로그램을 작성하세요.

Input

첫째 줄에 서버의 수 N(1≤N≤500,000)이 주어집니다.
이후 N-1개 줄에 각 케이블이 연결하는 서버 한 쌍의 번호들이 공백을 사이로 두고 주어집니다.
그 다음 줄에 NIA가 정해 놓은 서버의 수 K(0≤K<N) 가 주어집니다.
마지막 K개의 줄에 NIA가 정해 놓은 서버들의 번호들이 한 줄에 하나씩 주어집니다.

Output

만약 서버 전체를 마비시킬 수 있다면 첫째 줄에 1과 승현이가 공격해야 할 최소한의 서버 수를 한 칸씩 띄어 출력합니다. 만약 절대로 서버 전체를 마비시킬 수 없다면 0과 무용지물이 되지 않는 케이블의 수를 한 칸씩 띄어 출력합니다.

IO Example

입력

12
1 2
1 3
2 4
2 5
2 6
5 9
5 10
3 7
3 8
7 11
7 12
2
6
12

출력

1 4

입출력 보충
위 예제에서는 2, 3, 5, 7번 서버를 마비시키는 게 최소입니다.

출처:GENIUSainta.com

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]