22728번 - Amida, the City of Miracle 다국어

문제

奇跡の都市アミダ(Amida, the City of Miracle)の市長は他の市のように選挙で選ぶのではない.かつて長い政権闘争と天変地異により疲弊したこの都市は,候補者全員を公平に選び,かつ幸運の星の下に生まれた者を市長にするために,候補者全員の運命をくじにゆだねることにしたのである.後にあみだくじと呼ばれるくじである.

選挙は以下のように行われる.候補者数と同数の長い縦線が引かれ,さらにいくつかの横線がそこに引かれる.横線は隣接した縦線の途中同士を結ぶように引かれる.いずれかの縦線の下には「当選」と書かれている.どの縦線が当選であるかは候補者からわからないように隠される.それぞれの候補者は縦線を 1 つ選択する.全ての候補者の選択が終わると,各候補者は線を上から下に向かってたどる.ただし,移動途中に横線が見つかったときは,横線の接続された反対側の縦線に移り,また下に向かってたどる.縦線の一番下までたどり着いたときに,そこに「当選」と書かれていた者が当選して,次期市長となる.

この方法はうまくいった.幸運な市長の下に,争いも災害も少ない平和な時代が続いた.しかし近年,人口増加のためにこの手法に限界が見えてきた.候補者が増えたため,あみだくじが大規模になり,手作業による集計では非常に時間がかかるようになったのである.そこで市では,市役所のプログラマーであるあなたにあみだくじの電算化を依頼した.

あなたの仕事は,あみだくじの構造と,選択された縦線の位置が与えられたときに,最終的にどの縦線にたどり着くかを求めるプログラムを書くことである.

以下の図は,サンプルとして与えた入力および出力の内容を示したものである.

입력

入力は複数のデータセットからなる.1 つのデータセットは以下のように与えられる.

n m a
横線1
横線2
横線3
...
横線m

n ,m ,a はそれぞれ 2 ≤ n ≤ 100, 0 ≤ m ≤ 1000, 1 ≤ a ≤ n をみたす整数であり,それぞれ縦線の本数,横線の本数,調べる縦線の番号を表す.

横線のデータは以下のように与えられる.

h p q

h ,p ,q はそれぞれ 1 ≤ h ≤ 1000, 1 ≤ p < q ≤ n, を満たす整数であり,h はその横線の高さ,p ,q はその横線につながっている 2 本の縦線の番号を表す.

1 つの縦線の同じ高さに,異なる横線が 2 つ以上つくことはない.

入力の終わりには,空白で区切られた 3 つのゼロのみからなる行がある。

출력

それぞれのデータセットに対して 1 行ずつ,縦線 a の上端からたどったときの下端における縦線の番号を出力しなさい.

제한

힌트