In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
In the Mysterious Land of Worms there are many worm-houses. Not all of them are inhabited. It is known however, that at most one worm lives in each house. Some pairs of houses are connected with a path. For any pair of two different houses there exists exactly one route consisting of paths, so that none of the paths repeats on the route.
One day, all of the worms decided to meet in one of the houses. They agreed that every hour each of them will move along a path leaving the house it is presently in and will go to the other house at the opposite end of that path (walking along any path in the Mysterious Land of Worms takes exactly one hour). Worms intend to continue their travel untill the moment, when all of them meet in the same house (they need to be in that house exactly in the same time).
Unfortunately, worms have not foreseen that it may take a long period of time to meet if they apply this method of movement. Sometimes it is even impossible to meet. That is why worms asked you for help with verifying whether their meeting can be arranged and if so, how long it will take to meet in the best case.
Write a program which:
The first line of the standard input contains two integers and (, ), separated with a single space and denoting accordingly the number of houses and the number of paths in the Mysterious Land of Worms. Houses are numbered with natural numbers ranging from to . Following lines contain descriptions of paths. Each of them consists of two integers and (), separated with a single space and denoting numbers of houses connected with a given path. Description of paths is followed by a line containing one integer (), denoting the number of worms living in the Mysterious Land of Worms. Each of the following lines contains one integer () denoting the house where the -th worm lives.
The first and only line of standard output should contain only one word NIE (i.e. no in Polish), if worms cannot meet while moving according to the rules, or one integer equal to the number of hours required by all worms to get to the meeting place.
For the input data:
6 5 1 2 2 3 2 4 4 5 4 6 3 2 5 6
the correct result is:
Task author: Jakub Radoszewski.