#K63502. Origins of Rumors
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
.
3
5 4
1 2
2 3
3 4
4 5
5 0
3 2
1 2
2 3
1
No rumors
1
</p>