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

Uolevi liikkuu mielellään raitiovaunuilla ja haluaisi päästä niillä mahdollisimman moniin paikkoihin.

Uolevi on paraikaa etsimässä uutta asuntoa, jonka tietysti täytyy sijaita raitiovaunupysäkin kohdalla. Lisäksi Uolevi haluaa, että pysäkiltä pääsee mahdollisimman monelle muulle pysäkille.

Tehtäväsi on etsiä Uoleville optimaalinen asuinpaikka.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: pysäkkien määrä ja yhteyksien määrä. Pysäkit on numeroitu kokonaisluvuin 1,2,\ldots,n.

Tämän jälkeen syötteessä on m riviä, joista jokainen kuvaa yhden yhteyden. Jokainen yhteys on kaksisuuntainen, ja saman pysäkkiparin välillä on enintään yksi yhteys.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako pysäkkiä on Uolevin tavoitettavissa, jos hän valitsee asuinpaikkansa optimaalisesti.

Rajat

  • 1 \le n \le 10^5
  • 1 \le m \le 10^5

Esimerkki

Syöte:

6 4
1 2
1 3
1 4
6 5

Tuloste:

4

Selitys: Jos Uolevi menee asumaan pysäkin 1, 2, 3 tai 4 kohdalle, hän pystyy matkustamaan kaikille kyseisille pysäkeille.