CSES - Teatterit
  • Time limit: 4.00 s
  • Memory limit: 128 MB
Uolevin setä on aikeissa perustaa kaksi elokuvateatteria kaupunkiin. Hän on kuitenkin säästäväinen mies ja ostaa jokaista elokuvaa vain yhden nauhan. Siksi jokaisen elokuvan ensi-ilta on teatterissa 1 päivää aiemmin kuin teatterissa 2.

Jos joku asiakas huomaisi, että teatteri 2 näyttää elokuvia päivän myöhemmin, se tekisi huonoa teatterin maineelle. Niinpä tehtäväsi on valita teattereille sellaiset paikat, että ei ole olemassa mitään reittiä teatterista 1 teatteriin 2.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $m$: risteysten määrä ja teiden määrä. Risteykset on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden tien. Rivillä on kaksi kokonaislukua $a_i$ ja $b_i$: mistä risteyksestä tie alkaa ja mihin se päättyy. Kaikki tiet ovat yksisuuntaisia.

Tuloste

Ohjelmasi tulee tulostaa kaksi kokonaislukua: risteykset, joihin teatterit sijoitetaan (ensin teatteri 1, sitten teatteri 2). Jos vaihtoehtoja on useita, voit tulostaa minkä tahansa niistä. Ainakin yksi ratkaisu on aina olemassa.

Rajat
  • $1 \le n \le 5 \cdot 10^4$
  • $1 \le m \le 5 \cdot 10^4$
  • $1 \le a_i, b_i \le n$
Esimerkki

Syöte:
4 5
1 2
1 3
2 4
4 3
2 3


Tuloste:
3 1

Selitys: Risteyksestä 3 ei pääse risteykseen 1, joten teatterin 1 voi sijoittaa risteykseen 3 ja teatterin 2 risteykseen 1.