Şəhərcik#5476
Şəhərdə nəqliyyat problemləri mövcuddur. Bir çox insan piyada gəzməkdən çəkinir və avtomobilə üstünlük verir. Problem ondadır ki, küçələr dar, avtomobillər isə genişdir. Əgər iki avtomobil əks istiqamətlərdə hərəkət edirsə, tıxac yaranır. Buna görə də bütün küçələrin bir tərəfli olmasına qərar verilib. Lakin kifayət qədər yol nişanı yoxdur, buna görə də sizin köməyinizə ehtiyac var.
Sizə şəhərin xəritəsi, planlı qraf kimi təqdim olunub. Bütün küçələrin istiqamətlərini müəyyən etməlisiniz, lakin məhdudiyyətləri unutmamalısınız: Hər bir zirvədən ən çox üç ox çıxmalıdır (daxil olan oxların sayı məhdud deyil). Digər aspektlər (məsələn, zirvələrin əlçatanlığı və ya güclü bağlılıq) sizi narahat etməməlidir. Əgər bir neçə həll yolu varsa, istənilən birini təqdim edə bilərsiniz.
Girişin ilk sətri iki tam ədəd və (1 \leq N \leq 200\,000, 1 \leq M \leq 1\,000\,000) ehtiva edir, burada zirvələrin sayını, isə kənarların sayını göstərir. Sonrakı sətir kənarları təsvir edir. Hər bir kənar iki qonşu zirvənin və (1 \leq i, j \leq N) nömrələri ilə təsvir edilir. Qrafın planlı olması təmin edilir, yəni onu müstəvi üzərində (zirvələr — nöqtələr, kənarlar — seqmentlər) elə çəkmək mümkündür ki, heç bir iki seqment kəsişməsin (ümumi zirvələr istisna olmaqla). Bu qrafda döngələr və çoxlu kənarlar yoxdur.
Nəticələr girişdəki formatda çıxarılır. Yalnız bu dəfə kənarlar istiqamətlidir ( -dən -yə kənarı göstərir). Əgər verilmiş qraf üçün həll yolu yoxdursa, çıxışda no sətrini çıxarın.
Nümunə 1