EN - Entrapment

no tags 

Example The separatist leader General Grievous, the second in command of Count Dooku, comes to know that Chancellor Palpatine’s convoy, escorted by Obi-wan 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 one-way 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 one-way connection from planet p to planet q.

Output Description

The output should contain t lines. The ith line corresponds to the ith test case. The output for the ith 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: 2020-08-11 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: 2018-08-01 21:34:42

Nice Problem (:

Last edit: 2018-08-02 17:08:11
fegla: 2017-04-07 17:35:53

m ≤ 119407 not m ≤ 100011

fire_heart: 2016-08-05 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: 2015-10-08 18:23:32

add c++14 please!!!!!

Hussain Kara Fallah: 2014-03-04 20:58:26

done in o(n+m) :D

karan173: 2013-11-23 08:53:06

Weak test cases, my program won't even pass the example given in picture, still got AC

Shaka Shadows: 2011-09-06 03:33:34

@amaroq is right. I got RE (SIGSEV) with the constraints given in the text.

amaroq: 2009-06-01 07:56:43

WARNING: the input contains cases where m>100011!


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