Worms

In the mysterious Land of Worms there are many worm-houses. Not all of them are inhabited, and each house holds at most one worm. Some pairs of houses are joined by a path. For every pair of distinct houses there is exactly one route made of paths on which no path is used twice, so the houses and paths together form a tree.

One day all of the worms decide to gather in a single house. They agree that, at the start of every hour, each worm walks along one path out of the house it is currently in and reaches the house at the other end of that path (walking along any path takes exactly one hour). A worm must move every hour and can never stay in place. The worms keep moving until the moment when every one of them is in the same house at the same time.

Meeting this way can take a long time, and sometimes it is impossible. Help the worms find out whether a meeting can be arranged and, if it can, how many hours it takes in the best case.

Write a program that:

• reads the description of the Land of Worms from standard input,
• decides whether the worms can meet and, if so, the least number of hours it takes,
• writes the answer to standard output.

The first line contains two integers $n$ and $m$ ($2 \le n \le 50000$, $1 \le m \le 50000$), separated by a single space, denoting the number of houses and the number of paths. Houses are numbered from $1$ to $n$.

Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$), separated by a single space, describing a path that connects houses $a$ and $b$.

The next line contains one integer $k$ ($2 \le k \le n$), the number of worms. Each of the following $k$ lines contains one integer $d$ ($1 \le d \le n$), the house in which one worm lives. No two worms live in the same house.

Print a single line. If the worms can never all meet under these rules, print the word NIE (Polish for no). Otherwise print one integer: the least number of hours needed for all worms to gather in one house.