Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Kääntäjät

Kääntäjät


View task | Model solution | Statistics


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
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->2, 2->3, 3->1 sekä 2->4. Tällöin myös käännös 3->4 onnistuu seuraavasti: 3->1->2->4.