Masala #0421

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.

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.

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.