주사위 게임

시간 제한3초메모리 제한128 MB

요약

n명의 선수 사이에서 치른 m개의 경기(무향 다중 그래프)가 주어질 때, 각 경기의 승자를 정해 어떤 선수도 k번을 초과해 이기지 않도록 하는 최소 k를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 이분 탐색, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

주사위 게임은 두 사람이 벌이는, 승패가 순전히 운에 달린 놀이다. 최근 바이트오티아 전역에서 인기가 높아지고 있으며, 수도에는 주사위 게임 애호가들을 위한 전용 클럽까지 생겼다. 클럽 회원들은 서로 이야기를 나누다가 이따금 무작위로 정해진 상대와 좋아하는 이 게임을 즐긴다. 하루 동안 가장 많이 이긴 사람은 '행운아' 칭호를 얻는다. 조용한 밤에는 몇 판밖에 열리지 않기도 하는데, 그런 날에는 단 한 번의 승리만으로도 행운아가 될 수 있다.

어느 날, 지지리도 운이 없던 바이트아사르가 이 영예로운 칭호를 차지했다. 그는 너무 놀란 나머지 자신이 몇 판을 이겼는지조차 까맣게 잊어버렸다. 그날 밤 누구와 누가 몇 판을 두었는지는 정확히 기억하지만, 각 판의 결과는 알지 못한다. 바이트아사르는 행운아 칭호를 얻기 위해 필요했던 최소 승수가 얼마인지 궁금해한다.

다시 말해, 각 판의 승자를 마음대로 정할 수 있다고 할 때, 어떤 선수도 $k$ 번을 넘겨 이기지 않도록 만들 수 있는 가장 작은 정수 $k$ 를 구하면 된다.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 공백 하나로 구분되어 주어진다 ( $1 \le n \le 10\,000$ , $0 \le m \le 10\,000$ ). $n$ 은 선수의 수, $m$ 은 진행된 게임의 수이다. 선수는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. 이어지는 $m$ 개의 줄에는 각 게임에 참가한 두 선수의 번호가 공백 하나로 구분되어 주어진다. 같은 쌍이 여러 번 등장할 수 있다.

출력

각 게임의 승자를 적절히 정하여 어떤 선수도 $k$ 번을 초과해 이기지 않도록 만들 수 있는 가장 작은 정수 $k$ 를 한 줄에 출력한다.

예제3

예제 1
입력
```
4 4
1 2
1 3
1 4
1 2
```
예상 출력
```
1
```
예제 2
입력
```
3 3
1 2
2 3
3 1
```
예상 출력
```
1
```
예제 3
입력
```
4 3
1 2
1 3
1 4
```
예상 출력
```
1
```