Minimum City Selection

You are given a directed graph with n cities and m one-way roads. Each road connects from one city to another. Your task is to determine the minimum number of cities that need to be chosen such that for every pair of chosen cities, there is a path from one to the other.

In other words, if the entire graph is strongly connected, you can choose just one city. Otherwise, you need to choose at least two cities. Formally, a directed graph is strongly connected if for every two cities u and v, there exists a directed path from u to v and a directed path from v to u.

You may assume that the cities are numbered from 1 to n and that there are no self-loops or multiple edges.

The decision can be summarized by the following formula in \(\LaTeX\):

[ \text{answer} = \begin{cases} 1, & \text{if } G \text{ is strongly connected} \ 2, & \text{otherwise} \end{cases} ]

</p>

inputFormat

The input is given from stdin and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Where n is the number of cities, m is the number of directed roads, and each of the next m lines contains two integers u and v representing a road from city u to city v.

outputFormat

Output a single integer to stdout: output 1 if the entire graph is strongly connected, otherwise output 2.

## sample

5 7
1 2
2 3
3 4
4 5
5 1
1 3
3 5

1