Anders the cat has been hired to clean the snow of the streets of Heavy Metal City. He drives a cleaning machine of the well-known brand Blue-White Tree, and when he gets his machine stuck he removes the snow using a shovel made of the best wood around extracted from Quad Segment Trees, and the best steel out of Manowar factories. His lazyness doesn’t allow him to work too much; therefore he does not want to pass the same street more than once. He has a map of the neighbourhood he needs to clean: it is mainly built of streets and intersections.
Due to the fierce traffic the streets of Heavy Metal City can be traversed only in their original direction in the aim to avoid any accident. Because the aim of Anders, the Mayor of the city is strongly thinking to stop the traffic a time enough to clean the city, allowing Anders to traverse streets in both directions.
Given the number of intersections and the streets between them, tell Anders if he can clean all the streets without passing more than once on any of them. Also you must tell him, if the traffic stopping is needed or not.
The first line contain a integer number 1 ≤ T ≤ 100 representing the amount of cases. For each one:
- The first line contains two space-separated integer numbers 1 ≤ N ≤ 50 and 0 ≤ M ≤ N*(N-1): the amount of intersections and streets respectively. The intersections are conveniently numbered between 1 and N. And the cleaning machine can start and finish in arbitrary intersections.
- The following M lines contains two space-separated integer numbers A and B (1 ≤ A, B ≤ N, A != B), to describe a street going from intersection A to intersection B.
If Anders can clean the city normally as he wants output "YES". If the traffic stopping is needed in order to complete the aim of Anders output "TRAFFIC STOPPING NEEDED". Otherwise output "WAKE UP EARLIER"
3 2 2 1 2 2 1 4 3 1 2 1 3 1 4 3 3 1 2 1 3 2 3
YES WAKE UP EARLIER TRAFFIC STOPPING NEEDED
- 2 seconds
Problem source: COJ