BREAK - Breaking in

no tags 

Mayco has recently been hired as a security consultant for a well-known software company. At the moment, he's working on his first assignment – trying to determine which of the company's servers would be the best targets for potential attackers. It is a bit difficult, though, because some of the servers "trust" some of the others. If an attacker compromises a server, he or she can also freely access all servers that trust it (and servers that trust them, and so on).

By definition, the importance of a server S is the number of servers the attacker would be able to access if he compromised S. The most important servers are those with the highest importance. (Note that there can be more than one most important server. This is also illustrated in the example below.)

Problem specification

The network consists of N computers, numbered 1 to N, inclusive. The trust between computers is described by M ordered pairs (A, B) of numbers, denoting that computer A trusts computer B. The trust is not assumed to be mutual – i.e., if a computer A trusts computer B, it does not necessarily imply that computer B trusts computer A.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing the numbers N and M (1 <= N <= 9000, 1 <= M <= 52000). Each of the following M lines contains two integers, A and B, denoting that computer A trusts computer B.

Output specification

For each test case, the output shall contain one line with the numbers of all of the most important servers. The numbers must be listed in increasing order and separated by single spaces.

Example

input:
2

5 4
3 1
3 2
4 3
5 3

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

output:
1 2
4

Note

Blue Mary has found a pruning which will make the program very efficient. So the time limit of the hard test case is changed from 60 seconds to 15 seconds. If you have some even harder test case, please send it to me, and I'll add it to the standard input file.


hide comments
secundus: 2020-05-25 12:32:33

For those struggling, try this test case I made:
6 6
1 2
3 2
3 4
2 4
2 5
5 6
Answer: 6
Make sure you are reversing the DAG and searching properly.

vinty: 2020-03-27 23:48:34

Nice problem. Makes you dive deep into SCC. Really enjoyed it. AC 0.09

luvkumbi: 2020-02-02 20:24:41

@tieuchanlong.....even i am getting WA.....what are the new test cases u found which are causing WA ?

rofiqul: 2019-08-02 07:47:13

i donot know why i get runtime error

subashsroy: 2019-07-14 03:14:29

Make sure you print in ascending order

sarthakshah30: 2017-05-31 22:22:19

Nice Implementation Problem.
SCC

tieuchanlong: 2016-11-19 17:02:59

Do you guys have any testcase.I got WA...

Pramod : 2016-08-07 14:53:55

getting WA, admin could you check why I am getting WA, id = 17454677.

Thanks

lynx_: 2016-06-26 11:58:49

Its not...linear solution will definitely pass..
Mine passed in 0.11

Last edit: 2016-06-26 12:01:06
shubham7iitj: 2015-09-19 11:58:42

Time limit is very strict. Linear time solutions also not passing.


Added by:Fudan University Problem Setters
Date:2008-05-24
Time limit:0.5s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IPSC 2008