Masala #0421

Xotira 128 MB Vaqt 1000 ms Qiyinchiligi 60 %
14

  

Sayohatchi Azimjon

Azimjon Baytlandiya mamlakatiga sayohat qilmoqchi u mamlakatning barcha shaxarlariga borishni istaydi. Baytlandiyada jami \(N\) ta shahar mavjud bo'lib shaxarlar 0 dan \(N-1\) gacha raqamlangan va \(N\) ta shaharni \(K\) ta yo'llar bog'lab turadi. Azimjon Baytlandiya mamlakatining xaritasini ko'zdan kechirar ekan bir qiziqarli narsani sezib qoldi ya'ni \(u_i\) va \(v_i\) shaharlarni bog'lab turuvchi yo'l mavjud bo'lsa, \(u_i\) dan \(v_i\) shaharga borish mumkun lekin \(v_i\) dan \(u_i\) shaharga bu ikki shaharni bog’lab turuvchi yo’ldan qaytib bo’lmasligini sezdi. Endi Azimjon Baytlandiyaning barcha shaxarlariga sayohat qilishni istamaydi, u shunday bir shaxarni topishni hoxlaydiki u shaxardan istalgan bir shaxarga borish mumkun bo’lsin.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son \(N, K (2 \le N+K \le 5*10^5)\) mos ravishda shaharlar soni va yo'llar soni. Kiyingi \(K\) ta satirda \((u_i, v_i)\) \((0 \le u_i,v_i \le N-1)\) juftliklar \(u_i\) shahardan \(v_i\) shaharga borish mumkunligi.


Chiquvchi ma'lumotlar:

Azimjon Baytlandiyaning istalgan bir shaxriga borish mumkun bo’lgan shaxar raqamini chop eting. Agar bunday shaharlar bir nechta bo'lsa eng kichikgini, mavjud bo'lmasa -1 ni chop eting.


Misollar
# input.txt output.txt
1
5 5
0 3
1 2
3 1
4 0
4 1
4
2
5 5
0 3
2 1
3 1
4 0
4 1
-1
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin