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

문제

Valstybei priklauso 2ドル \times N$ salų (sunumeruotų nuo 1ドル$ iki 2ドルN$), 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.

서브태스크

힌트