Məqalə#3877
2048-ci ildə sosioloqlar rəqabətli proqramçılar cəmiyyətinin strukturu ilə maraqlandılar və araşdırmaları nəticəsində aşağıdakı müşahidələri etdilər. Hər hansı bir iştirakçının uğuru barədə xəbər onun hər hansı tanışı tərəfindən bütün tanışlarına çatdırıla bilər (bəlkə də başqa adamlar vasitəsilə). İki nəfər yalnız bir-birilərini tanıyırlarsa ünsiyyət qururlar və belə olduqda da yalnız hər ikisinin tanıdığı insanlar barədə danışırlar, lakin özləri haqqında yox. Bundan əlavə, hər hansı bir şəxsin tanışlarına baxdıqda, onların arasında elə üçlük yoxdur ki, bu üç nəfərin heç biri bir-birini tanımasın.
İndi isə cəmiyyət bir araya gələrək yeni alqoritmin təsvir olunduğu və kvadrat matrisləri Θ(N^2.32768) vaxtda hasilə vura bilən məqalənin lisenziya haqqını ödəmək qərarına gəldi (burada N matrislərin ölçüsüdür). Heç də təəccüblü deyil ki, lisenziya şərtləri məqalənin surətinin çıxarılmasını qəti qadağan edir. Hər kəs məqaləni oxumaq istəyir, amma heç kim onu tanımadığı adama verməyə razı deyil. Üstəlik, hamının vaxtı azdır və məqaləni oxuduqdan sonra onunla məşğul olmaq istəmirlər. Yeganə istisna Vasya-dır: məqalənin sahibi odur, o, ortaq pulla bir nüsxə alıb və hamı oxuduqdan sonra onu saxlayacaq. Amma o da yalnız məqaləni sonuncu oxuyandan arxivləşdirmək üçün götürməyə razıdır, onu birindən digərinə daşımaq istəmir.
Yuxarıdakı şərtlər altında məqaləni oxuya biləcək maksimal sayda insanın neçə olduğunu və məqaləni oxumaq üçün hansılar ardıcıllıqla ötürülməli olduqlarını tapın.
Bütün proqramçılar müsbət tam ədədlərlə nömrələnib və Vasyanın nömrəsi 1-dir.
Birinci sətirdə iki tam ədəd — proqramçıların sayı N və tanış proqramçılar üçün cütlüklərin sayı M verilir (3 ≤ N ≤ 1000, 0 ≤ M ≤ 10 000, M ≤ N(N-1)/2). Növbəti M sətrin hər birində iki tam ədəd — tanış proqramçıların nömrələri p_1 və p_2 (1 ≤ p_1, p_2 ≤ N, p_1 ≠ p_2) verilir.
Birinci sətrə məqaləni oxuya bilən proqramçıların sayını göstərən tam ədəd K yazın. Növbəti sətrə isə bu adamların hansı sırayla məqaləni oxuyacağını göstərin. Bu ardıcıllıq 1 ilə başlamalı, heç bir nömrə təkrar olunmamalı, ardıcıl iki nömrə tanış proqramçılara aid olmalı və son proqramçı da Vasya ilə tanış olmalıdır.
Nümunə 1