I. Instagraph
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A celebrity in a social network is somebody with many followers, but who doesn't follow them back. More precisely, a person is a celebrity for a group of people, if

  • every member of the group follows the person,
  • the person follows nobody in the group.
The celebrity centrality of person $$$v$$$, written $$$\mathrm{CC}(v)$$$, is the maximum size of such a group.

We model the social network as a directed graph with $$$N$$$ vertices $$$1$$$, $$$\ldots$$$, $$$N$$$. A directed edge from $$$u$$$ to $$$v$$$ means that person $$$u$$$ follows person $$$v$$$. For example, in

Sample Input 1
we have $$$\operatorname{CC}(1) = 0$$$, $$$\operatorname{CC}(2) = 1$$$, and $$$\operatorname{CC}(5) = 2$$$.

Your task is to find a vertex $$$v$$$ with the maximum celebrity centrality $$$\mathrm{CC}(v)$$$. In case of a tie, choose the smallest $$$v$$$.

Input

The input consists of

  • One line with two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 200\,000$$$, $$$0 \le M \le 1\,000\,000$$$), the number of vertices and the number of directed edges.
  • $$$M$$$ lines with two distinct integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$), indicating a directed edge from $$$u$$$ to $$$v$$$. There are no duplicate edges.
Output

Output two integers: the smallest $$$v$$$ with the maximum celebrity centrality and the value $$$\mathrm{CC}(v)$$$.

Examples
Input
6 8
1 2
2 1
2 3
3 2
3 6
4 5
5 2
6 5
Output
5 2
Input
1 0
Output
1 0