URI Online Judge | 1692

Curo Attack

By Jose Miguel Noblecilla, Pontificia Universidad Católica del Perú PE Peru

Timelimit: 1

A new university network is composed by N servers distributed around the campus, every pair of servers are connected by an unique path made of wires and are N - 1 wires, but the Informatics Deparment has forgotten assign a server to the mathematics faculty.

A lazy mathematics student, named Curo, is feeling resentful, because now he can't run his programs in a powerful machine. So, he decided to implant a tricky virus, designed by him during his free time, because he hates his theoretical mathematics courses and prefer coding something more fun rather than write down boring numbers and symbols.

Curo wants to infect the maximum number of servers and take his revenge upon the Informatics Department. He prepared a simulation of the attack before the real one, but his computer isn't powerful enough to execute it. So, he needs your help for this task, but first you have to know how the virus works.

If the virus infect a server, his adjacents servers will be infected too. Also, the virus program has a pseudo-random variable named Kuro-number. At the end of the infection process, the largest distance between two infected servers must be exactly the Kuro-number.

Given a test network and a Kuro-number you must obtain if exists the maximum number of infected servers, otherwise you must print "Impossible Revenge!"


There are several tests, the first line of each test contains two integers N and K --- number of servers in the network and the Kuro-number (2K < N1000). Next N - 1 lines contain N - 1 wires of that network --- Each line contains a pair (u, v) means there is an connection between server u and server v (1u,vN).


Print if exists the maximum number of infected servers, otherwise you must print "Impossible Revenge!".

Sample Input Sample Output

9 3
1 2
2 7
2 3
2 4
4 5
4 6
4 8
8 9

5 3
1 2
2 3
2 4
2 5

Impossible revenge!