Yol nişanları
Fərqli ölkələr yol nişanlarının fon rəngləri üçün müxtəlif seçimlər edir. Məsələn, Rusiyada şəhər yollarında nişanların fonu ağ, kənd yollarında mavi, avtomagistrallarda isə yaşıl olur. Avropada avtomagistral nişanları bəzən mavi fonlu, ABŞ-da isə əksər hallarda yaşıl fonludur.
Flatland kralı bir gün ölkə ətrafında səyahət edərkən yolunu itirdi və bu ona yeni bir ideya verdi. O, avtomagistral yol nişanlarının fon rəngləri üçün yeni bir qayda tətbiq etmək istəyir. Flatlandda n şəhər mövcuddur və bu şəhərlər m ikitərəfli avtomagistrallarla birləşdirilib. Hər hansı bir şəhərə ən çox d avtomagistral təsadüf edir. Kralın planına əsasən, avtomagistrallardakı nişanlar d+1 fərqli fon rəngindən birinə sahib olacaq. Qayda belədir ki, eyni şəhərə təsadüf edən heç bir iki avtomagistral eyni fon rənginə malik olmamalıdır. İslahatdan sonra avtomagistralda bir nişan gördüyünüzdə yalnız yola çıxdığınız şəhəri xatırlamalısınız və dərhal hansı şəhərə gedəcəyinizi başa düşəcəksiniz (əgər mükəmməl yaddaşınız varsa).
Flatlanddakı avtomagistralların planı verildikdə, kralın hansı avtomagistralın hansı nişan fon rənginə sahib olacağını müəyyən etməsinə kömək edin.
Giriş verilənləri
Giriş faylının ilk sətri üç tam ədəd n, m və d (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ d ≤ n-1) ehtiva edir. Növbəti m sətir avtomagistralları təsvir edir, hər bir avtomagistral onu birləşdirən şəhərlərin nömrələrindən ibarət iki tam ədəd ilə təsvir olunur. Heç bir şəhərə d-dən çox avtomagistral təsadüf etmir.
Çıxış verilənləri
Əgər eyni şəhərə təsadüf edən heç bir iki avtomagistrala eyni rəng təyin edilməyəcək şəkildə 1 ilə d+1 arasında rəngləri avtomagistrallara təyin etmək mümkün deyilsə, çıxış faylının ilk sətrində -1 çıxarın.
Əks halda, avtomagistrallara təyin edilməli olan rəngləri (giriş faylında avtomagistralların təsvir edildiyi sırayla) göstərən m tam ədəd çıxarın.