수업 시간이 따분했던 선용이는 노트에 이리저리 선을 그으며 지루함을 달래고 있었다. 그러던 중 한가지 놀이를 생각해냈는데, 이는 다음과 같다.

1. $1, 2, ... , n$의 번호가 매겨진 $n$개의 정점을 그려 놓는다.
2. $1 ≤ u, v ≤ n$이고 $u ≠ v$인 $u$번 정점과 $v$번 정점을 골라, 둘을 잇는 간선을 추가한다.
• 지금까지 $u$번 정점과 $v$번 정점을 직접적으로 잇는 간선은 존재하지 않았다.
3. 지금까지 그려진 그래프 상에 사이클이 존재한다면 즉시 놀이를 종료한다.
4. 그렇지 않다면 $2$로 돌아간다.

선용이는 $n$이 작을 경우 육안으로 쉽게 놀이를 할 수 있었지만, $n$이 커질 경우 육안으로 놀이를 진행하기에 다소 어려움을 느꼈다. 선용이를 위해 위 놀이를 시뮬레이션하는 프로그램을 작성해주자!

첫째 줄에 정점의 개수 $n$과 추가한 간선의 개수 $m$이 공백으로 구분되어 주어진다. $(3 ≤ m ≤ n ≤ 100,000)$

둘째 줄부터 $m$개의 줄에 걸쳐 추가되는 간선 정보가 순서대로 주어진다. 각 정보는 $u, v$가 공백으로 구분되어 주어지며, 정점 $u$와 정점 $v$를 잇는 간선이 추가된다는 의미이다. $(1 ≤ u, v ≤ n)$

네 번째 간선을 추가한 순간 $1, 2, 3$번 정점을 잇는 사이클이 발생한다.