D_1 - On/Off Switch

配点: 400点

問題文

$1$ から $N$ までの番号が付いた $N$ 個のマスがあります。また、スイッチは $M$ 個あり、それぞれのスイッチはマス $C_j (1≦ j ≦M)$ にあります。
全てのスイッチにON/OFF の $2$ つの状態があります。最初スイッチは OFF です。また、全てのスイッチは共有されており、ひとつのスイッチの状態が変化するとすべてのスイッチも同様に変化します。

くしらくんはマス $1$ にコマを置き、以下の操作を $K$ 回行いました。

今コマがいるマスを $x$ としたとき、

• スイッチが OFF ならば、コマを $A_x$ に移動させ、移動した先にスイッチがあるならばそれを $1$ 回押す。
• スイッチが ON ならば、コマを $B_x$ に移動させ、移動した先にスイッチがあるならばそれを $1$ 回押す。

$K$ 回の操作を終えた後、コマはどのマスにいるか答えてください。

制約

• $1 ≦ M ≦ N ≦ 10^5$
• $1 ≦ K ≦ 10^{18}$
• $1 ≦ A_i, B_i ≦ N$
• $1 ≦ C_j ≦N$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力してください。

入出力例1

• 入力

4 2 3
2 4 3 1
4 1 1 2
2 4

• 出力

4

コマは、$1$(OFF)→$2$(ON)→$1$(ON)→$4$(OFF) と移動します。

入出力例1

• 入力

1 1 10000000000
1
1
1

• 出力

1

操作を行ってもコマの位置が変わらない場合があります。