시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 2048 MB20181789.474%

문제

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

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$.

입력

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 two integers: the smallest $v$ with the maximum celebrity centrality and the value $\mathrm{CC}(v)$.

예제 입력 1

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

예제 출력 1

5 2

예제 입력 2

1 0

예제 출력 2

1 0

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2025 I번

  • 문제를 만든 사람: Pål Grønås Drange