There are N hills numbered 1 to N. You need to reach peak of hill N. Some of these hills are connected by one way rope bridges, and these rope bridges are the only way to reach hill N and return back to hill 1. Each rope bridge disappears after being used once. Some rope bridges do not lead to hill N, and some lead to hill N but without a way to return back to hill 1. You MUST use all the rope bridges in this journey from hill 1 to N and back to 1. If multiple ropes are connecting two hills then it should be counted multiple times and all of the ropes available must be used exactly once. You must check whether the hills are safe to climb or they are a trap!
Input:
The first line contains T: the number of test cases. Each test case contains N and M separated by space. Next M lines contains v1, v2 separated by a space where v1 and v2 represent the hills connected by a rope bridge.
Output:
Output T lines. For each test case, either print "Possible!!" or, if it's a trap, "Danger!!" without quotes.
Note that it is possible to travel safely, only when there exists a way to travel, such that all of the M rope bridges are used exactly once, and the journey starts at 1, and ends at 1.
Constraints:
1<=T<=15
1<=N<=100000
0<=M<=2 * 100000
In the first test case: N=4, M=4.
There is a path from 1->2->3->4->1 which uses all the ropes and returns back to hill 1. Therefore, it's safe so output should be "Possible!!".
In the second test case: N=4, M=3.
There is no path which leads to hill 4 and returns back to hill 1. Therefore, it's a trap so output should be "Danger!!".
