Сигурно веќе сте слушнале дека Мендо (познатиот член на Комисијата за натпревари) и Кибид (надалеку прочуениот систем инженер од ФИНКИ) не се сакаат многу. Во оваа задача, слично како и на претходниот натпревар, ќе разгледуваме една бркотница помеѓу Мендо и Кибид. Овојпат, бркотницата ќе се случува во лабораториите на Факултетот за информатички науки и компјутерско инженерство (ФИНКИ).

Распоредот на лабораториите на ФИНКИ е објаснет во продолжение. Сите лаборатории на факултетот се наоѓаат во главниот ходник на факултетот, и секоја лабораторија има по точно една основна врата преку која од ходникот може да се влезе во неа. Дополнително, некои од лабораториите се поврзани едни со други со споредни врати кои водат директно од една лабораторија во друга. И Мендо и Кибид ја познаваат поврзаноста на факултетот, но само Кибид се движи низ споредните врати.

Иницијално, Кибид се наоѓа во една од лабораториите на факултетот (Мендо не знае во која). Мендо го бара Кибид така што влегува во една лабораторија од факултетот преку нејзината основна врата и проверува дали Кибид се наоѓа во таа лабораторија. Доколку Кибид се наоѓа во таа лабораторија, Мендо го фотографира со својот специјален смартфон (*). Доколку Кибид не се наоѓа во таа лабораторија, Мендо излегува од неа и оди во главниот ходник од каде одлучува во која лабораторија ќе влезе следно. Тогаш, Кибид го користи времето кое му е потребно на Мендо да одлучи во која лабораторија ќе влезе следно за да се премести во некоја од лабораториите која е директно поврзана со лабораторијата во која тој се наоѓа во дадениот момент. Кибид никогаш не останува во истата лабораторија.

Знаеме дека Мендо ќе го искористи неговото познавање на распоредот на лабораториите и ќе подготви најдобра можна стратегија. Напишете програма која ќе пресмета колку најмалку лаборатории, при примена на стратегијата, во најлош случај, треба да отвори Мендо, за со сигурност да го слика Кибид. На пример, нека факултетот има две лаборатории и нека тие се поврзани меѓусебно со споредна врата. Тогаш, Мендо може да го слика Кибид, во најлош случај, после 2 отворања на една иста лабораторија (доколку Кибид не се наоѓа во лабораторијата при нејзиното прво отворање, сигурно ќе се наоѓа таму при второто отворање - бидејќи тој никогаш не останува во истата лабораторија).

(*) Забелешка: Во оригиналниот текст на задачата, наместо да го слика, Мендо го фаќа Кибид и го прекршува од ќотек, но заради непромовирање на насилство тоа го заменивме! :)

Влез

Во првата линија се запишани два цели броја N и K (2 ≤ N ≤ 21, 1 ≤ K ≤ 210), кои го означуваат бројот на лаборатории и споредни премини, соодветно.

Во секоја од следните K линии се запишани по два цели броја Ai и Bi (1 ≤ Ai < Bi ≤ N), кои означуваат дека постои спореден премин од лабораторијата Ai до лабораторијата Bi (и обратно). Ниту еден пар лаборатории не се појавува повеќе од еднаш. Лабораториите се така поврзани да секогаш постои спореден пат (пат низ споредни врати) од која било лабораторија X до која било друга лабораторија Y.

Забелешка: Во тест случаи кои вредат најмалку 30% од поените, ќе важи 2 ≤ N ≤ 10.

Излез

Во првата линија од стандардниот излез отпечатете колку најмалку лаборатории, во најлош случај, треба да отвори Мендо, за со сигурност да го слика Кибид. Во втората линија отпечатете кои лаборатории треба да ги отвори Мендо. Доколку постојат повеќе такви решенија, отпечатете го лексикографски најмалото. За една листа од броеви велиме дека е лексикографски помала од друга доколку првиот број во кој се разликуваат двете листи е помал во првата листа.

Доколку не постои решение кое гарантира дека Мендо ќе го фати Кибид, отпечатете "-1" (види пример 2).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
2 1
1 2

излез
2
1 1

влез
3 3
1 2
1 3
2 3

излез
-1

влез
5 4
3 5
2 4
1 2
1 5

излез
6
2 1 5 2 1 5

Објаснување за вториот пример: Без разлика во кои лаборатории и по кој редослед ќе влегува Мендо, не постои решение кое гарантира дека тој ќе го фати Кибид.