Kağızdan qələmi qaldırmadan
Gəlin məşhur bir tapmacanı xatırlayaq: kağızdan qələmi qaldırmadan bir şəkil çəkmək, bu zaman hər xətti yalnız bir dəfə çəkmək olar (yəni, əvvəllər çəkilmiş xətt üzərində qələmi aparmaq olmaz).
Hamımızın uşaqlıqda çəkməyə çalışdığımız ən məşhur belə bir şəkil açıq zərfdir.
Beləliklə, qələmi kağızdan qaldırmadan və hər xətti yalnız bir dəfə çəkərək belə bir zərfi çəkmək üçün nömrələnmiş nöqtələri, məsələn, belə bir ardıcıllıqla birləşdirmək olardı: 1 4 2 5 4 3 2 1 5.
Budur, yuxarıda təsvir olunan qaydalara uyğun olaraq çəkilə bilən başqa bir şəkil nümunəsi.
Sizə nöqtələr və onları birləşdirən xətlər dəsti kimi bir şəkil təsviri veriləcək. Proqramınız qələmi kağızdan qaldırmadan və hər xətti dəqiq bir dəfə çəkərək bu şəkili çəkməyin mümkün olub-olmadığını müəyyən etməlidir. Diqqət yetirin ki, başqa heç bir nöqtə ilə xəttlə birləşdirilməmiş ayrıca qoyulmuş bir nöqtəni çəkmək üçün qələmi kağızdan qaldırmaq lazımdır.
Giriş verilənləri
Giriş mətn faylının ilk sətirində boşluqla ayrılmış iki tam ədəd N və M yazılmışdır. N - şəkildəki nöqtələrin sayı (2 ≤ N ≤ 200), M - onları birləşdirən xətlərin sayı (0 ≤ M ≤ N·(N-1)/2). Bütün nöqtələr 1 -dən N -ə qədər ədədlərlə nömrələnmişdir. Hər bir xətt nöqtələrin nömrələri ilə - bu xətti birləşdirən nöqtələrin cütü ilə verilir.
Giriş faylının növbəti M sətiri xətlərin təsvirlərini ehtiva edir. Hər bir sətir boşluqla ayrılmış iki natural ədəd A və B ehtiva edir (1 ≤ A, B ≤ N, A ≠ B). Bu, müvafiq xətti birləşdirən nöqtələrin nömrələridir. İstənilən iki nöqtə bir xəttdən çox birləşdirilə bilməz.
Çıxış verilənləri
Əgər giriş faylında verilmiş şəkil şərtlərdə təsvir olunan qaydalara uyğun olaraq çəkilə bilərsə, çıxış mətn faylında xətlərlə birləşdirilməsi lazım olan nöqtələrin nömrələrinin ardıcıllığını boşluqla ayıraraq çıxarmaq lazımdır.
Əgər şəkili çəkmək mümkün deyilsə, yeganə -1 (mənfi bir) ədədini çıxarmaq lazımdır.