IM - Intergalactic Map


Map Jedi knights, Qui-Gon Jinn and his young apprentice Obi-Wan Kenobi, are entrusted by Queen Padmé Amidala to save Naboo from an invasion by the Trade Federation. They must leave Naboo immediately and go to Tatooine to pick up the proof of the Federation’s evil design. They then must proceed on to the Republic’s capital planet Coruscant to produce it in front of the Republic’s Senate. To help them in this endeavor, the queen’s captain provides them with an intergalactic map. This map shows connections between planets not yet blockaded by the Trade Federation. Any pair of planets has at most one connection between them, and all the connections are two-way. To avoid detection by enemy spies, the knights must embark on this adventure without visiting any planet more than once. Can you help them by determining if such a path exists?

Note - In the attached map, the desired path is shown in bold.

Input Description

The first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions of the test cases follow one after the other. The first line of each test case is a pair of positive integers n, m (separated by a single space). 2 ≤ n ≤ 30011 is the number of planets and m ≤ 50011 is the number of connections between planets. The planets are indexed with integers from 1 to n. The indices of Naboo, Tatooine and Coruscant are 1, 2, 3 respectively. The next m lines contain two integers each, giving pairs of planets that have a connection between them.

Output Description

The output should contain t lines. The ith line corresponds to the ith test case. The output for each test case should be YES if the required path exists and NO otherwise.

Example

Input
2
3 3
1 2
2 3
1 3
3 1
1 3

Output
YES
NO


hide comments
kesh4281: 2020-03-29 08:49:29

m can be greater than 50011,
but n<=30011 is satisfied
also there can be edges with out of range indexes.
while adding an edge x-y simple ignore them if out of range
if(x<0||y<0||x>n||y>n)
continue;

Last edit: 2020-03-29 08:50:28
joqsan_77: 2018-08-14 22:18:50

What a disappointing problem.

1. "The planets are indexed with integers from 1 to n". This is FALSE. In the real (no spojtoolkit) test cases there are vertices with indices above n. If in your code you're not allocating space for the maximum number of vertices right from the get go, then check the range of the vertices u, v in the input of edge (u, v), and discard those edges, whose vertices are above n.

This costed me a couple of RunTime Errors.

2. "...must embark on this adventure without visiting any planet more than once". This is FALSE. Otherwise it would mean that we have to check for a vertex-disjoint path from 1 to 3, passing necessarily through 2. As you can elaborate, this in turn would mean that for every vertex u in the original graph we create u_in and u_out and build a new graph accordingly. I did this and got WA. Then I dismissed completely this part and just check for an edge-disjoint path from 1 to 3, passing through 2 and got AC.

This explains why the test cases of Augusto below return YES (which is what the testing system actually checks for, when checking for edge-disjoint paths) instead of NO (assuming that statement is true and checking for vertex-disjoint paths).

Last edit: 2018-08-14 22:21:53
Augusto: 2015-06-25 00:45:23

Karlvin is right, test cases are weak.

I submitted a solutiong that returns YES for cases like:
5 5
2 4
2 5
4 1
5 1
1 3

and
6 6
1 4
4 6
6 2
2 5
5 4
4 3

According to the problem description, the answer for those cases should be NO.
Correct solution according to the problem also got accepted though...

Last edit: 2015-06-25 00:45:47
Haojian Ma: 2014-03-30 15:34:04

Some m seem more than 50011

Deepak Chittajallu: 2014-02-17 22:46:40

The test cases seem to have out of range vertex indices. I got a segmentation fault. This should have been mentioned in the problem statement. I ignored edges with out of range vertex indices and my solution was accepted.

Karlvin: 2013-05-16 12:54:14

I get "accepted" while I find a case" 5 5 2 4 2 5 4 1 5 1 1 3" proving my program wrong. What is the answer supposed to be? My accepted-solution says "YES".

Shaka Shadows: 2010-08-03 13:38:45

Is not funny when we have to deal with values in the test data out of ranges specified in text :(. Too many RE because of that.

Rafa³ Bielenia: 2010-06-10 16:02:45

As others said vertex numbers > n. Beware!

Max: 2010-05-28 17:09:23

Be careful of ids >n

Last edit: 2010-05-28 17:09:48
Brian Bi: 2009-12-23 21:44:24

The old C++ is still allowed, but the new C++ 4.3.2 isn't, presumably due to a bug in the system. (Either that, or the author actually didn't check the "include new languages" box...)


Added by:Kashyap KBR
Date:2006-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Resource:Fair Isaac Programming Challenge - prelims 2006