Jane likes cycles. One day she gets a tree. Jane plans to make some changes on it. She hopes that after adding some edges, its each vertex will only belong to exactly one cycle. Besides, she also hopes that there won’t exist self-loops. Because she thinks the self-loop is not a normal cycle. In order to prevent Jane wasting time on some impossible things, please tell her whether she can finish her plan or not in advance.

There are multiple cases.

For each case, the first line is an integer N (1<=N<=10⁵), indicating Jane’s tree has N vertices. Then following N – 1 Lines. Each line contains two integers Ai,Bi (1<= Ai,Bi<=N), indicating there is an edge between Ai and Bi.

It’s guaranteed that the input data will form a tree.

For each case, output “Possible” if Jane can finish her plan, otherwise output “Impossible”.