30086번 - Svarbiausiasis tiltas 서브태스크다국어

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.