Problem : 180 - 蟲蟲集結

Problem Statistics

Solved Member: 30　　Submission: 145　　User Tried: 34

Statement:

HH種了一顆有50000個點的樹，樹上面有很多蟲住在任意點上。

這些蟲很愛蠕動，必須以每小時一條邊的速度在樹上蠕動(不能停下來，除非所有蟲都聚集在某一點開雞絲會)，蠕動時會從一個點滾到另一個點。

一年一度的雞絲會指日可待，牠們想找一個點作為牠們的集會所，以討論今年要怎麼一起雞絲，HH只好問問你最少要幾個小時才可以使牠們聚集在某個點順利開會。

Input:Output:

第一行有兩個數字N, M，表示這棵樹有N個點與M條邊
第2行到第M+1行每行兩個數字u, v，代表點u與點v有條長度為1的邊
接下來有一個數字K，代表有K隻蟲
然後有K行，每行一個數字Xi，代表第i隻蟲住在點i

輸出一個數字表示最少要幾小時才能全聚集到同一個聚集地，如果不行請輸出"NIE"

Sample Input:Sample Output:

6 5
1 2
2 3
2 4
4 5
4 6
3
2
5
6

HINT:

Source:

PA 2006

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6-1	1000ms	65536kb	10
6-2	1000ms	65536kb
7-1	1000ms	65536kb	10
7-2	1000ms	65536kb
8-1	1000ms	65536kb	10
8-2	1000ms	65536kb
9	1000ms	65536kb	10
10	1000ms	65536kb	10