가장 중요한 다리

한 나라에 $2 \times N$개의 섬이 있으며, 섬에는 $1$번부터 $2N$번까지 번호가 붙어 있다. 이 섬들은 $M$개의 다리로 연결되어 있다.

관광객을 더 끌어들이기 위해 나라는 가장 중요한 다리를 하나 골라 매일 밤 다른 색으로 밝히기로 했다.

가장 중요한 다리는 폐쇄했을 때 나라가 섬의 수가 같은 두 지역(각각 정확히 $N$개의 섬)으로 나뉘고, 한 지역에서 다른 지역으로 다리를 건너 갈 수 없게 되는 다리라는 제안이 있었다.

$N$, $M$과 다리의 연결 정보가 주어졌을 때, 가장 중요한 다리를 구하라.

첫 줄에 정수 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄에는 각각 공백으로 구분된 두 정수 $i$와 $j$($i \ne j$)가 주어지며, 이는 $i$번 섬과 $j$번 섬이 다리로 연결되어 있음을 뜻한다.

가장 중요한 다리의 번호를 출력한다.

• $1 \leq N \leq 5\,000$
• $0 \leq M \leq 100\,000$
• $2 \times N + M \leq 100\,000$
• 데이터는 다음 조건을 만족한다:
  • 두 섬을 잇는 다리는 최대 하나이다;
  • 어느 섬에서든 다리를 건너 다른 모든 섬으로 갈 수 있다;
  • 가장 중요한 다리는 항상 존재한다.