LCC/Moose '18 Contest 3 S5 - Santa's Helper

View as PDF

Submit solution

Points: 15
Time limit: 2.0s
Memory limit: 128M

Problem type

Santa realized that he will have to work his magic in order to deliver all the presents this year. It turns out that "work his magic" means hiring a second, secret Santa to help him deliver some of the presents. Of course, he cannot let this secret get out or Christmas would be ruined!

One particular challenge will be flying between places. Suppose Santa and his helper are both at the north pole and they want to fly to the south pole. They cannot both visit the same city in their journeys as kids would notice that there is more than one Santa flying around. Hence, the paths that they would take need to visit completely separate cities.

Santa and his helper travel exclusively from city to city, pole to pole, pole to city, or city to pole as their sleighs are powered by the spirit of Christmas, which is most plentiful in cities. Also, they cannot travel between some locations as the areas between them contain dangerous characters (such as Grinch and Jack) trying to shut down Christmas.

Santa will need to make trips between the two poles in many different parts of the world. For each part of the world, you are given the cities of the world and the routes that Santa and his helper can take. Can you figure out whether both Santa and his helper can reach the south pole by flying through that part of the world without their secret being revealed?

Input Specification

The first line of input contains an integer T (1 \le T \le 10), the number of parts of the world that Santa wants to fly through. For each part of the world, the input looks as follows: The first line of input contains two integers N, M (2 \le N, M \le 100,000) the number of locations and the number of pairs of locations that a Santa can travel between. Locations are numbered from 1 to N, where 1 is the north pole, N is the south pole, and cities are numbered 2 through N-1. The next M lines each contain two integers A, B (1 \le A, B \le N), which say that Santa and his helper can travel between locations A and B.

Output Specification

For each part of the world, output "Yes" if it is possible for both Santa and his helper to travel between the poles without visiting the same city, or "No" otherwise.

Sample Input

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

Sample Output



There are no comments at the moment.