Internet Problem Solving Contest

IPSC 2008

Problem B – Breaking in

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. 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.



5 4
3 1
3 2
4 3
5 3

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

In the first test case, compromising one of the servers 1 and 2 gives us access to the entire network.

In the second test case, compromising server 4 gives us access to servers 1, 2, and 3. All other servers are less important.