Masala #0421

Xotira 128 MB Vaqt 1000 ms Qiyinchiligi 60 %
3.6 (Baholar 5)
14

  

Sayohatchi Azimjon

Azimjon Baytlandiya mamlakatiga sayohat qilmoqchi u mamlakatning barcha shaxarlariga borishni istaydi. Baytlandiyada jami NN ta shahar mavjud bo'lib shaxarlar 0 dan N1N-1 gacha raqamlangan va NN ta shaharni KK ta yo'llar bog'lab turadi. Azimjon Baytlandiya mamlakatining xaritasini ko'zdan kechirar ekan bir qiziqarli narsani sezib qoldi ya'ni uiu_i va viv_i shaharlarni bog'lab turuvchi yo'l mavjud bo'lsa, uiu_i dan viv_i shaharga borish mumkun lekin viv_i dan uiu_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(2N+K5105)N, K (2 \le N+K \le 5*10^5) mos ravishda shaharlar soni va yo'llar soni. Kiyingi KK ta satirda (ui,vi)(u_i, v_i) (0ui,viN1)(0 \le u_i,v_i \le N-1) juftliklar uiu_i shahardan viv_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