Uolevi on voittanut lentoyhtiön kilpailun ja saa lentää ilmaiseksi minkä tahansa lentoreitin. Reitti voi muodostua useista peräkkäisistä lennoista. Uolevi haluaa tietenkin valita reitin, jossa on mahdollisimman monta kaupunkia.

Uolevi haluaa lentää Syrjälästä Lehmälään, ja tehtäväsi on etsiä tällainen reitti, jossa on mahdollisimman monta kaupunkia. Sinulle on annettu lista mahdollisista lennoista. Tiedät, että lentojen muodostama verkko on syklitön.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: kaupunkien määrä ja lentojen määrä. Kaupungit on numeroitu 1,2,\ldots,n. Syrjälän numero on 1, ja Lehmälän numero on n.

Sitten syötteessä on m riviä, joista jokainen kuvaa yhden lennon. Rivillä on kaksi kokonaislukua a ja b: lento kulkee kaupungista a kaupunkiin b. Jokainen lento on yksisuuntainen.

Tuloste

Tulosta ensin "10-4", jos jokin reitti on olemassa, ja muuten "QAQ".

Jos reitti on olemassa, tulosta sitten suurin mahdollinen määrä kaupunkeja reitillä. Tulosta sen jälkeen kaikki kaupungit reitin varrella. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

• 2 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le a,b \le n

Esimerkki

Syöte:

5 5
1 2
2 5
1 3
3 4
4 5

Tuloste:

10-4
4
1 3 4 5