Svarbiausiasis tiltas

시간 제한1초메모리 제한1024 MB

요약

연결된 2N개 정점 그래프에서 제거하면 정확히 N개씩 두 영역으로 나뉘는 단절선을 찾는다.

난이도: 보통10점 중 7점
유형: 그래프, DFS, 트리, 동적 계획법
정답자: 아직 제출이 없습니다

문제

Valstybei priklauso $2 \times N$ salų (sunumeruotų nuo $1$ iki $2N$ ), kurias jungia $M$ tiltų. Siekiant pritraukti daugiau turistų, buvo nuspręsta išrinkti svarbiausiąjį tiltą ir jį kasnakt apšviesti vis kitomis spalvomis.

Buvo pateiktas pasiūlymas, kad svarbiausiasis miesto tiltas turėtų būti tas, kurį uždarius valstybė taptų padalinta į du regionus, turinčius vienodą skaičių salų (t. y. lygiai po $N$ ), ir nebūtų įmanoma sausuma nuvykti iš vieno regiono į kitą.

Duoti $N$ , $M$ bei salų sujungimo tiltais schema. Raskite svarbiausiąjį tiltą.

입력

Pirmojoje eilutėje pateikti sveikieji skaičiai $N$ ir $M$ . Kitose $M$ eilučių pateikiama po du tarpais atskirtus skaičius $i$ ir $j$ ( $i \ne j$ ), kurie reiškia, kad $i$ -toji ir $j$ -toji salos yra sujungtos tiltu.

출력

Išveskite svarbiausiojo tilto numerį.

제한

$1 ≤ N ≤ 5\\,000$
$0 ≤ M ≤ 100\\,000$
$2 \times N + M ≤ 100\\,000$
Duomenys tokie, kad:
- Dvi salas jungia ne daugiau kaip vienas tiltas;
- Iš bet kokios salos galima tiltais nukeliauti į bet kokią kitą salą;
- Svarbiausiasis tiltas visada egzistuos.

예제1

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