Instagraph

문제

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 $vv$, written $\mathrm{C}\mathrm{C}(v)\backslash mathrm\{CC\}(v)$, is the maximum size of such a group.

We model the social network as a directed graph with $NN$ vertices $11$, $\dots \backslash ldots$, $NN$. A directed edge from $uu$ to $vv$ means that person $uu$ follows person $vv$. For example, in

we have $\mathrm{CC}(1)=0\backslash operatorname\{CC\}(1)\; =\; 0$, $\mathrm{CC}(2)=1\backslash operatorname\{CC\}(2)\; =\; 1$, and $\mathrm{CC}(5)=2\backslash operatorname\{CC\}(5)\; =\; 2$.

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

입력

The input consists of

• One line with two integers $NN$ and $MM$ ($1\le N\le 2000001\; \backslash le\; N\; \backslash le\; 200\backslash ,000$, $0\le M\le 10000000\; \backslash le\; M\; \backslash le\; 1\backslash ,000\backslash ,000$), the number of vertices and the number of directed edges.
• $MM$ lines with two distinct integers $uu$ and $vv$ ($1\le u,v\le N1\; \backslash le\; u,v\; \backslash le\; N$), indicating a directed edge from $uu$ to $vv$. There are no duplicate edges.

출력

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

6 8
1 2
2 1
2 3
3 2
3 6
4 5
5 2
6 5

5 2

1 0

1 0