Problem I
Instagraph

• 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

Figure 1: 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)$.

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

5 2

1 0

1 0