지렁이

신비한 지렁이 나라에는 지렁이 집이 많이 있다. 모든 집에 지렁이가 사는 것은 아니며, 한 집에는 많아야 한 마리의 지렁이가 산다. 일부 집 쌍은 길로 연결되어 있다. 서로 다른 두 집을 고르면 같은 길을 두 번 지나지 않는 경로가 정확히 하나 존재한다. 즉, 집과 길은 전체적으로 하나의 트리를 이룬다.

어느 날 모든 지렁이가 한 집에 모이기로 했다. 매 시간마다 각 지렁이는 지금 있는 집에서 길 하나를 따라 이동하여 그 길의 반대쪽 끝에 있는 집으로 간다(어떤 길이든 지나가는 데 정확히 한 시간이 걸린다). 지렁이는 매 시간마다 반드시 이동해야 하며 제자리에 머무를 수 없다. 지렁이들은 모두가 같은 시각에 같은 집에 있게 되는 순간까지 계속 이동한다.

이 방법으로 모이는 데는 아주 오랜 시간이 걸릴 수 있고, 때로는 모이는 것이 불가능하기도 하다. 지렁이들이 모일 수 있는지, 모일 수 있다면 최선의 경우 몇 시간이 걸리는지 알아내는 것을 도와주자.

다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 지렁이 나라의 정보를 읽는다.
• 지렁이들이 모일 수 있는지, 모일 수 있다면 최소 몇 시간이 걸리는지 판단한다.
• 답을 표준 출력에 쓴다.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다($2 \le n \le 50000$, $1 \le m \le 50000$). 각각 집의 수와 길의 수를 나타낸다. 집은 $1$번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $m$개의 줄에는 각각 두 정수 $a$와 $b$가 공백 하나로 구분되어 주어진다($1 \le a, b \le n$). 이는 집 $a$와 집 $b$를 잇는 길을 나타낸다.

그다음 줄에는 지렁이의 수를 나타내는 정수 $k$가 주어진다($2 \le k \le n$). 이어지는 $k$개의 줄에는 각각 한 정수 $d$가 주어지며($1 \le d \le n$), 한 지렁이가 사는 집을 나타낸다. 어떤 두 지렁이도 같은 집에 살지 않는다.

한 줄을 출력한다. 규칙에 따라 지렁이들이 결코 모두 모일 수 없다면 NIE(폴란드어로 아니오)를 출력한다. 그렇지 않으면 모든 지렁이가 한 집에 모이는 데 필요한 최소 시간을 정수 하나로 출력한다.