CSES - Kääntäjät
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Käännöstoimisto on aloittanut toimintansa, mutta sen palveluksessa ei ole vielä yhtään kääntäjää. Sinulle on annettu tiedot, mistä kielistä mihin kieliin toimiston täytyy pystyä tekemään käännöksiä.

Jokainen palkattava kääntäjä pystyy tekemään käännöksiä vieraasta kielestä äidinkieleensä. Tarvittaessa käännös voidaan tehdä myös useamman kääntäjän yhteistyönä. Esimerkiksi jos A kääntää suomesta saksaan ja B kääntää saksasta ranskaan, niin A ja B pystyvät kääntämään yhdessä suomesta ranskaan.

Mikä on pienin määrä kääntäjiä, joiden avulla kaikki käännökset pystytään tekemään? Voit olettaa, että mille tahansa kieliparille voidaan palkata kääntäjä. Jokainen kääntäjä voi kääntää yhdestä kielestä yhteen kieleen.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: kielten määrä ja vaatimusten määrä. Kielet on numeroitu 1,2,\ldots,n.

Tämän jälkeen syötteessä on m riviä, joista jokainen sisältää kaksi kokonaislukua a_i ja b_i. Tämä tarkoittaa, että toimiston täytyy pystyä tekemään käännös kielestä a_i kieleen b_i. Sama vaatimus ei esiinny monta kertaa.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako kääntäjää täytyy palkata.

Rajat

  • 1 \le n \le 10^5
  • 1 \le m \le 10^5
  • 1 \le a_i, b_i \le n
  • a_i \neq b_i

Esimerkki

Syöte:

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

Tuloste:

4

Selitys: Yksi ratkaisu on palkata kääntäjät kielille 1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 1 sekä 2 \rightarrow 4. Tällöin myös käännös 3 \rightarrow 4 onnistuu seuraavasti: 3 \rightarrow 1 \rightarrow 2 \rightarrow 4.