CSES - Bussilinja
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Kaupunki muodostuu n risteyksestä ja m tiestä. Kaupunkiin halutaan perustaa bussilinja, joka kulkee katuja pitkin ja ohittaa joukon risteyksiä. Linjan tulee alkaa samasta risteyksestä kuin mihin se päättyy ja siinä tulee olla vähintään kolme risteystä.

Tehtäväsi on selvittää, voiko linjaa muodostaa, ja jos voi, antaa esimerkki, miten linjan voi muodostaa.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: risteyksien määrä ja katujen määrä. Risteykset on numeroitu 1,2,\ldots,n.

Sitten syötteessä on m riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua a ja b: katu lähtee risteyksestä a ja päättyy risteykseen b. Jokainen katu on yksisuuntainen, ja se alkaa ja päättyy eri risteyksessä.

Tuloste

Tulosta ensin "10-4", jos linjan voi muodostaa, ja muuten "QAQ".

Jos linjan voi muodostaa, tulosta sitten kokonaisluku k: risteyksien määrä reitillä. Tulosta lopuksi järjestyksessä jokainen reitillä oleva risteys. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

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

Esimerkki

Syöte:

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

Tuloste:

10-4
4
2 1 3 2