Nangijala

Astrid Lindgren의 소설 Bröderna Lejonhjärta에서는 죽은 뒤 Nangijala로 가게 된다. Nangijala에서 죽으면 Nangilima로 가게 된다. Nangilima에서는 죽을 수 없고 모두가 조화롭게 살아가지만, Nangilima 너머에 더 많은 세계가 존재한다고 생각해 볼 수도 있다.

이 문제에는 1, 2, 3, ....로 번호가 매겨진 세계가 무한히 많이 존재한다. 모든 사람은 처음에 세계 1에 있으며, 누군가가 세계 $i$에서 죽으면 세계 $i+1$로 가게 된다.

현재 세계 1에는 $N$명의 사람이 있다. 이 사람들 중에는 서로 적인 쌍이 $M$개 있다. 적들은 서로를 매우 싫어하기 때문에 가능하면 서로 다른 세계에 있고 싶어 한다. 적대 관계는 대칭 관계이다. 즉, 사람 $a$가 사람 $b$의 적이라면 $b$도 $a$의 적이다.

어떤 사람도 자신의 적과 같은 세계에 있지 않도록 하는 데 필요한 최소 사망 횟수를 구한다.

점수

해결한 코드는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1      |  11  |  $N \le 100\,000,$ 각 사람에게는 적이 최대 한 명 있다

2      |  36  |  $N \le 100\,000,$ 각 사람에게는 적이 최대 두 명 있다

3      |  26  |  $N \le 10,$ 적 관계 그래프는 트리이다

4      |  27  |  $N \le 100\,000,$ 적 관계 그래프는 트리이다

첫째 줄에 양의 정수 $N$와 $M$가 주어진다. 이어서 정수 $a_i$, $b_i$ $(0 \le a_i, b_i < N, a_i \neq b_i)$가 적힌 $M$개의 줄이 주어지며, 이는 $a_i$와 $b_i$가 서로 적이라는 뜻이다.

하나의 수 -- 어떤 적끼리도 같은 세계에 있지 않도록 하는 데 필요한 최소 사망 횟수 -- 를 출력한다.