All submissions for this problem are available.
Tannenbaum Jr. is a diligent networks administrator. He takes care of the university dormitory's networks as though they were his little children. The dormitories are spread out across the university campus and each dorm has its own sub-network. The nodes on the network are directionally connected.
In his effort to maintain the network, Tanny Jr. is interested in writing a little script. With his script, he wishes to find out the correctness of the interconnecting wires in his network. His script should send out a packet which should pass through each wire in the network just once, noting down the status of that wire.
Before Tanny begins to write such a script, he wants you to determine if it's even possible to send out a packet which should pass through each wire in the network just once, given the university's network configuration. Can you help him out?
First line contains, 1<=t<=5, the number of test cases, and then t cases follows,
The first line of each test case contains two integers n, number of nodes and m, number of wires connection the nodes, where 1<=n<=100 and 1<=m<=10000.
The next m lines contains two integers each, x y, which implies node x is directionally connected to the node y through wire.
Corresponding to each case, Print "POSSIBLE" (without accompanying double quotes), if possible and "NOT POSSIBLE" (without accompanying double quotes), if not possible.
Input: 2 6 6 0 1 1 2 2 3 3 4 4 5 5 0 4 5 0 1 1 3 3 2 2 1 1 0 Output: POSSIBLE POSSIBLE
One possible path to follow for case 1 is: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0. All the wires are covered and only once if the nodes in the network are visited in this sequence.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, C99 strict, CPP 4.3.2, CPP 6.3, CPP14, GO, JAVA, NODEJS|
Fetching successful submissions
If you are still having problems, see a sample solution here.