EN  Entrapment
The separatist leader General Grievous, the second in command of Count Dooku, comes to know that Chancellor Palpatine’s convoy, escorted by Obiwan and Anakin, is scheduled to depart from Kashyyyk in the Middle Rim of the Universe to Alderaan. General Grievous is aware that there are multiple paths going via different sets of planets from Kashyyyk to Alderaan. To make his abduction attempt successful, he decides to send his robots to the planet closest to Kashyyyk, other than itself, which lies on all the possible paths from Kashyyyk to Alderaan. Since you have pledged your allegiance to Count Dooku, you need to help him identify this planet.
The planetary map which is given to you for this purpose consists of a set of oneway connections between planets. You also know that a pair of planets can have at most one connection between them in each direction and there is always a path from Kashyyyk to Alderaan.
Note: In the given example, the planet with index 5 is the required planet.
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 ≤ 100011 is the number of connections between planets. The planets are indexed with integers from 1 to n and the indices of Kashyyyk and Alderaan are 1, n respectively. Each of the next m lines contains two integers p,q, meaning that there is a oneway connection from planet p to planet q.
Output Description
The output should contain t lines. The i^{th} line corresponds to the i^{th} test case. The output for the i^{th} test case should be the index of the planet with the required property.
Example
Input
2
3 2
1 3
3 2
4 4
1 3
3 4
1 2
2 4
Output
3
4
hide comments
anjani_11:
20200811 11:01:32
This problem should be in needed 15 problems (SPOJ). Will recommend to read about algorithms on flow network, if stuck. O(m+n) is way to go.. 

joqsan_77:
20180801 21:34:42
Nice Problem (: Last edit: 20180802 17:08:11 

fegla:
20170407 17:35:53
m ≤ 119407 not m ≤ 100011 

fire_heart:
20160805 13:20:25
test cases are very weak!!! my solution is O(n(n+m)) and still got AC, pls update the cases 

José Carlos Gutiérrez:
20151008 18:23:32
add c++14 please!!!!! 

Hussain Kara Fallah:
20140304 20:58:26
done in o(n+m) :D 

karan173:
20131123 08:53:06
Weak test cases, my program won't even pass the example given in picture, still got AC 

Shaka Shadows:
20110906 03:33:34
@amaroq is right. I got RE (SIGSEV) with the constraints given in the text. 

amaroq:
20090601 07:56:43
WARNING: the input contains cases where m>100011! 
Added by:  Kashyap KBR 
Date:  20061010 
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 PASGPC PASFPC PERL PHP PIKE PRLGswi PYTHON RUBY SCM qobi SCM guile ST WHITESPACE 
Resource:  Fair Isaac Programming Challenge  prelims 2006 