34179번 - 여름에 계급이 올라가는 이유는? 서브태스크

여름에 계급이 올라가는 이유는? 더 위니까

고려대학교 정보대학의 알고리즘 동아리 ALPS의 회장인 서현이는 부원들간 계급을 통해 부원들을 감시하고자 한다. 먼저 동아리 신입생 $N$명을 $1$단계 부원이라 하자. 이 신입생들 중 $M$쌍(한 쌍은 두 명을 의미한다)은 서로 친구 관계이다.

서현이는 친구인 부원이 서로 모의해 반란을 일으킬 수 있다고 생각해, $M$쌍의 $1$단계 친구 관계 각각을 감시하는 $2$단계 부원 $M$명을 배치했다. 즉, $2$단계 부원 한 명은 친구 관계인 $1$단계 부원 두 명을 감시한다.

그런데 $1$단계 부원들의 친구 관계를 감시해야 할 $2$단계 부원들 사이에도 친구 관계가 형성되어 있었다! 조사 결과 어떤 두 명의 $2$단계 부원이 공통으로 감시하는 $1$단계 부원이 있는 경우, 그 두 명은 서로 친구 관계임을 알아냈다. 서현이는 마찬가지로 $2$단계 부원들도 감시해야 하므로, 모든 $2$단계 친구 쌍 에 대해 $3$단계 부원을 한 명씩 배치하였다.

이런 식으로 $i$단계 부원들에 대해, 어떤 두 명이 공통으로 감시하는 $i-1$단계 부원이 있는 경우 그 두 명은 서로 친구 관계이며, $i$단계 부원들의 모든 친구 쌍에 대해 두 명을 감시하는 $i+1$단계 부원을 배치한다.

이렇게 부원간의 계급과 단계를 나누어 감시 체계를 구축했음에도 서현이는 반란이 일어날까 불안해 직접 부원을 감시하고 싶다. 서현이는 어떤 $i$단계 부원들을 감시하기 위해 먼저 $i$단계 부원들을 모두 $2$차원 평면에 배치했다. 이후 모든 친구 쌍을 직선 모양의 전선으로 연결한 후 대화 정보를 알아내 반란을 일으키는지 판단한다. 그러나 두 전선이 서로 교차하면 정보가 꼬이게 되어 정상적으로 알아낼 수 없다는 문제가 있다. 만약 서현이가 $i$단계 부원 모두를 전선이 교차하지 않도록 $2$차원 평면에 배치할 수 있다면 $i$단계를 직접 감시할 수 있으며, 그렇지 않다면 직접 감시할 수 없다.

본인이 ALPS 회장을 하고 싶던 준서는 서현이가 감시할 수 없는 최소 단계까지 부원을 배치하고 싶다. 서현이가 감시할 수 없는 최소 단계 $K$를 구해보자.

단, 서현이가 신입생을 뽑을 때 원하는 대로 뽑았기 때문에, $1$단계는 직접 감시할 수 있다는 것이 보장된다.

첫 번째 줄에 $1$단계 부원의 수 $N(0\le N\le 10^5)$와 $1$단계 부원 중 친구 쌍의 수 $M(0\le M\le 3N-6)$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$줄에 걸쳐 친구를 이루는 두 명의 번호 $a,b(1\le a,b\le N$; $a\ne b)$가 공백으로 구분되어 주어진다. 이때, 한 번 주어진 쌍 혹은 순서만 바뀐 쌍은 다시 주어지지 않는다.

만약 서현이가 감시할 수 없는 최소 단계 $K$가 존재한다면 $K$를 $998\, 244\, 353$으로 나눈 나머지를 출력한다.

만약 모든 $K$에 대해 서현이가 감시할 수 있다면 Rebellion Failed!를 출력한다.

이 문제의 시간 제한이 $0.777$초인 이유는 이번 제7회 고려대학교 MatKor Cup: 2025 Summer, The FinAL이 $7$회 대회이기 때문이다.