IM - Intergalactic 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
Drew Saltarelli:
2009-12-15 18:42:42
why no C++? :( |
|
Tony Beta Lambda:
2009-10-06 07:29:29
Simply ignore them. |
|
Carlos Joa:
2009-09-10 04:16:16
So, how should we deal with the out-of-range vertices? |
|
Tony Beta Lambda:
2009-07-15 13:29:21
Some test cases has vertex number out of range (<=0 or >n). Is it part of Trade Federation's trap? :) Last edit: 2009-07-15 13:34:05 |
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 |