004 - 接触追跡

新種のウイルスの感染が拡大している． このウイルスはキャリアとの濃厚接触による感染リスクがあり， それはキャリアの症状の有無によらないことが知られている． このため，感染が確認された者やその疑いの強い者と濃厚接触があった者を特定して検査することが防疫上有効である． そこで，普段から人と人との接触を携帯電話上のアプリをもちいてすべて記録しておき， 感染確認時にはその記録に基づいて直接・間接の感染リスクがある人を特定するシステムを構築したい．

あなたは，こうしたシステムの開発を任された．そして，既に携帯電話側のアプリは完成させた． インストールしたアプリが， 同じアプリをインストールした携帯電話を持っている人との濃厚接触を検知すると， 両者の ID を情報収集センターに送信する．

あなたの次の仕事は，利用者の感染が確認されたときに， その感染者から直接的または間接的に感染したリスクがある利用者を特定するプログラムを作ることである．

システムの利用者の感染が確認されたら， それ以前のある期間 (感染性保持期間) 内に濃厚接触した利用者は感染の疑いがある． 感染が疑われる利用者がその後にまた別の利用者と濃厚接触していれば， その相手にもまた感染の疑いがある． こうして感染の疑いは繰り返し広がるものとする．

ある利用者の感染が確認されると，その利用者の ID と， その利用者がキャリアになった可能性がある時刻以降の， すべての利用者同士の濃厚接触の記録が入力として与えられる． 与えられた記録にある濃厚接触はすべて， 感染が確認された利用者の感染性保持期間内に起こったと仮定する． 出力は感染が確認された利用者から直接的または間接的に感染した疑いがある利用者の総数である．

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

m n p
a₁ b₁
…
a_n b_n

各データセットは三つの整数 m，n，p からなる行から始まる． m (1 ≤ m ≤ 100) は利用者の人数を表す． n (0 ≤ n ≤ 1000) は記録の件数を表す． p (1 ≤ p ≤ m) は感染が確認された利用者の ID を表す．

続く n 行には利用者同士の濃厚接触の記録が 1 行に 1 件ずつ時刻順に並んでいる． 各行は，ID が a_i と b_i の利用者の濃厚接触があったことを表す． ここで， 1 ≤ a_i ≤ m, 1 ≤ b_i ≤ m かつ a_i ≠ b_i である．

入力の終わりは三つのゼロからなる行で表される．データセットの個数は 50 を超えない．

各データセットについて， 感染が確認された利用者とその利用者から直接的または間接的に感染した疑いがある利用者の総数を出力せよ．

3 2 1
1 2
2 3
4 5 2
1 3
3 4
2 1
3 1
1 2
100 0 100
0 0 0

3
3
1