Ringteed

문제

Bytelandi pealinnas Bytetownis elab poiss nimega Bit, kellele meeldib oma kodulinnas ringi jalutada. Bytetowni teedevõrk koosneb $NN$ väljakust, mida ühendavad omavahel $MM$ tänavat. On teada, et igalt väljakult saab neid tänavaid mööda igale teisele väljakule.

Kui mõnelt väljakult alustades on võimalik mööda tänavaid liikudes samale väljakule tagasi jõuda ilma vahepeal ühtegi väljakut või tänavat korduvalt külastamata, nimetavad kohalikud sellist marsruuti ringteeks. Bytetowni teedevõrgu huvitav omadus on, et ükski väljak ei asu mitmel ringteel.

Bit leiutas just uue plaani, kuidas ta edaspidi jalutama hakkab. Iga päev astub ta oma majast välja selle ees olevale väljakule. Siis valib mõne sealt algava tänava ja läheb seda mööda järgmisele väljakule, kus ta valib uue tänava, mida mööda jälle edasi minna. Seejuures ei käi Bit ühe jalutuskäigu jooksul ühelgi väljakul korduvalt. Ta jätkab jalutamist, kuni jõuab väljakule, kust kõik tänavad viivad juba külastatud väljakutele. Siis kuulutab ta selle päeva jalutuskäigu lõppenuks ja sõidab bussiga koju tagasi.

Kirjutada programm, mis leiab, mitmel erineval väljakul Biti jalutuskäigud lõppeda võivad.

입력

Tekstifaili esimesel real on tühikutega eraldatud väljakute arv $NN$ ($2\le N\le 2000002\; \backslash le\; N\; \backslash le\; 200\backslash ,000$), tänavate arv $MM$ ($N-1\le M\le \frac{4}{3}NN\; -\; 1\; \backslash le\; M\; \backslash le\; \backslash frac\{4\}\{3\}N$) ja Biti maja ees oleva väljaku number S ($1\le S\le N1\; \backslash le\; S\; \backslash le\; N$).

Järgmisel $MM$ real on igaühel tühikuga eraldatud täisarvud $A_{i}A\_i$ ja $B_{i}B\_i$ ($1\le A_i\le N1\; \backslash le\; A\_i\; \backslash le\; N$, $1\le B_i\le N1\; \backslash le\; B\_i\; \backslash le\; N$, $A_i\mathrm{\ne }{B}_{i}A\_i\; \backslash ne\; B\_i$), mis tähendavad, et väljakute $A_{i}A\_i$ ja $B_{i}B\_i$ vahel on tänav. On teada, et mistahes kahe väljaku vahel on ülimalt üks tänav.

출력

Tekstifaili ainsale reale väljastada üks täisarv: nende väljakute arv, millel Biti jalutuskäigud lõppeda võivad.

3 2 2
1 2
2 3

2

4 4 3
1 2
2 3
3 4
4 1

2