#K63502. Origins of Rumors

    ID: 31767 Type: Default 1000ms 256MiB

Origins of Rumors

Origins of Rumors

You are given several test cases describing the spread of rumors in a city. In each test case, there are N people and M pieces of information about how rumors are spread. Each rumor transmission is represented by a pair of integers (A, B) indicating that person A spread the rumor to person B.

Your task is to determine, for each test case, the set of persons who are origins of the rumors. A person is considered an origin if they have spread a rumor but were not reported as having received the rumor from someone else. If no rumors were spread or if every rumor spawner has also received a rumor, output No rumors for that test case.

Note: The output for each test case must list the origins in increasing order separated by a single space or simply print No rumors if there are none.

The origins satisfy the property:

$$\text{origins} = \{ A \mid A \text{ spread a rumor and } A \notin \{B \mid (\cdot, B) \text{ is a rumor transmission}\} \}. $$

inputFormat

The first line contains an integer T representing the number of test cases.

Each test case begins with a line containing two integers N and M where:

  • N is the number of people in the city.
  • M is the number of rumor transmissions.

If M > 0, the next M lines each contain two integers A and B indicating that person A spread the rumor to person B. If M = 0, no additional lines follow for that test case.

outputFormat

For each test case, output a single line:

  • If there is at least one origin, print all origin numbers in increasing order separated by a single space.
  • If there are no rumor transmissions or no origins, print No rumors.
## sample
3
5 4
1 2
2 3
3 4
4 5
5 0
3 2
1 2
2 3
1

No rumors 1

</p>