Police Station
InterviewTime limit2sMemory limit1024 MB
In a directed graph, list every vertex from which all other vertices are reachable by following arrows forward.
- Level
Medium4 of 10
- Topics
- Graph, DFS, Implementation
- Solved
- No attempts yet
Problem
A network of hyperspace highways runs through the galaxy. Each highway is a one way corridor between two planets. The galactic government wants to choose a planet for a police station.
For the police to protect the whole galaxy, it must be possible to travel from the police station to every planet over the highway network.
The police do not need a highway route back. On the way back they are in no hurry, so they may take routes slower than a highway.
You are given the network of one way highways. Find every planet from which all other planets can be reached by some sequence of highways.
Input
The first line contains two integers and : the number of planets and the number of highways.
Each of the next lines contains two integers and , the numbers of the planets joined by the -th highway. That highway is one way and can only be used to travel from planet to planet .
- and for every .
- No two highways join the same pair of planets in the same direction. Two highways may join the same pair in opposite directions.
- In 30% of the test data, and .
Output
Print two lines. The first line holds the number of planets that are suitable for the police station. The second line holds the numbers of those planets in ascending order, separated by single spaces. If no planet is suitable, print an empty second line.