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

Kaupunki muodostuu nn risteyksestä ja mm 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 nn ja mm: risteyksien määrä ja katujen määrä. Risteykset on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: katu lähtee risteyksestä aa ja päättyy risteykseen bb. 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 kk: risteyksien määrä reitillä. Tulosta lopuksi järjestyksessä jokainen reitillä oleva risteys. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \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