1066 - Breaking in
Time Limit : 10 Second
Memory Limit : 128 MB
Submission: 138
Solved: 22
- Description
- 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
- 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<=10000,0<=M<100000) Each of the following M lines contains two integers, A and B, denoting that computer A trusts computer B. - Output
- 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.
- sample input
-
2 5 4 3 1 3 2 4 3 5 3 6 5 1 2 2 3 3 1 1 4 5 6
- sample output
-
1 2 4
- hint
- 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.
- source