Problem C - Where Could We Meet?
George is the CEO of a chain of stores. From time to time, George wants
to arrange meetings with workers from any store. He is not a fan of
the new technologies and prefers to talk directly with people.
These meetings always take place at the end of the work day. George
realized that due to rush hour, it is impossible to go from some stores
to the management building and get there on time.
Since each store also has a meeting room for the store manager to use,
George decided that his meetings could also take place at one of the
stores. However, workers from any store should be able to get to the
meeting place on time during rush hour.
Consider that you are given a set of directed connections between
stores. These connections represent roads that never have rush hour
problems at the end of the day.
A store s can be used to hold the meeting between George and the
workers if there is a path (using one or more connections) from all
other stores to s.
Your task is to determine how many stores George can use to meet
with the workers.
Input
The input is a directed map specified as follows:
- One line with two integers N and M, where N represents the number of stores and M the number of available directed connections between stores.
- A list of M lines where each line contains two integers
si and sj (with 1 ≤ si ≤ N and 1 ≤ sj ≤ N) that represent an available connection from store si to store sj.
Output
The output is a single integer with the number of stores from which
there is a path from all other stores.
Constraints
Sample Input 1
4 4
1 2
2 1
3 2
4 1
Sample Output 1
2
Sample Input 2
4 4
1 2
2 1
2 3
1 4
Sample Output 2
0