Permütasiya

Tutaq ki, lövhədə 1-dən N-ə qədər olan bəzi rəqəmlərin bir permutasiyası yazılıb və Pətəyin dəftərində isə bir neçə sıralı rəqəm cütü var, burada hər bir rəqəm 1-dən N-ə qədərdir və cütdəki rəqəmlər eyni ola bilməz. Əgər lövhədə yan-yana duran iki rəqəm, dəftərdəki cütlərdən birini eyni ardıcıllıqla təşkil edirsə, Pətəy lövhədəki bu iki rəqəmdən istənilən birini silə bilər. Bu zaman Pətəy hesab edir ki, silinmiş rəqəmi ayıran rəqəmlər indi yan-yana durur.

Tapşırıq

Pətəyin dəftərində yazılmış rəqəm cütləri üçün, rəqəmlərin başlanğıc permutasiyasını quracaq bir proqram yazın ki, oğlan ardıcıl silmələrlə onu tək bir rəqəmə endirə bilsin, ya da belə bir permutasiyanın mövcud olmadığını müəyyən etsin.

Giriş verilənləri

Giriş faylının ilk sətrində N və M (2 ≤ N ≤ 10^{5 }, 2 ≤ M ≤ 10^5) natural ədədləri yazılıb, burada M — Pətəyin dəftərində yazılmış sıralı cütlərin sayıdır. Növbəti M sətir hər biri iki rəqəm olan müvafiq cütlərin elementlərini ehtiva edir. Hər bir rəqəm naturaldır, N-i aşmır və cütdəki digər rəqəmdən fərqlidir. Verilmiş sıralı cütlər arasında eyni olanlar yoxdur.

Çıxış verilənləri

Çıxış faylının ilk sətrində Pətəyin tək bir rəqəmə endirə biləcəyi 1-dən N-ə qədər olan rəqəmlərin istənilən bir permutasiyasını yazmaq lazımdır və ikinci sətirdə isə Pətəyin ardıcıl olaraq sildiyi N-1 rəqəmin ardıcıllığını yazmaq lazımdır. Əgər tələb olunan permutasiya mövcud deyilsə, çıxış faylına yalnız 0 rəqəmi yazılmalıdır.

Nümunələr

Qiymətləndirmə

Test dəsti 3 blokdan ibarətdir, burada əlavə olaraq aşağıdakı şərtlər yerinə yetirilir:

1. 20 % xal: 2 ≤ N ≤ 5.

2. 35 % xal: 5 < N ≤ 1000.

3. 45 % xal: 1000 < N ≤ 10^5.

İzah. Permutasiyada 1 3 4 2, üçü silə bilərik, çünki 3 4 cütümüz var. Sonra lövhədəki rəqəmlərin ardıcıllığı belə olur: 1 4 2. İndi dördü silə bilərik, çünki 1 4 cütümüz var. Lövhədə 1 2 cütü qalır. Bu cüt də Pətəyin dəftərində olduğundan, məsələn, birini silə bilərik və lövhədə tək bir rəqəm qalır (bu halda — 2).