あらすじ
マジシャンがいた。マジシャンはコップとボールを使ったマジックをした。
まずボールにコップを被せてコップを何回か入れ替える。そのあとボールがどのコップにあるか選んでもらう。しかし選んだところにボールは入っておらず、別のコップにあるというマジックである。
r1910は、ボールがどこにあるか選ぶことになった。r1910は空気が読めないので、ボールがどこにあるかを全力で当てたいと思った。
執念の捜査の末マジシャンはコップを入れ替えているときにボールを入れ替えていることが分かったが、分かったところでボールのあるコップを絞れなかった。
あなたが代わりにボールが入っている可能性があるコップの数を求めてほしい。
問題
入れ替えが終わったあとにボールが入っている可能性のあるコップの数を出力せよ。
ボールの移動は、入れ替えるコップ同士でしか行われない。
入力
n m r a1 b1 a2 b2 . . . . ar br
１行目にコップの数$n$と最初にボールが入っているコップの番号$m$が半角空白区切りで与えられる。
２行目にコップを入れ替える回数$r$が与えられる。
続く$r$行に入れ替えるコップの番号$a$$i$,$b$$j$が与えられる。
制約
すべての入出力ケースにおいて以下を満たす。
- 3≦n≦100 1≦m≦n 1≦r≦100 1≦ai＜bj≦n
※a1=b1となる場合はありませんが、a1=a2やa1=b2となる場合はあります。
入出力例
入出力例1
3 2 1 1 3
出力例1
1
入力例2
3 2 2 1 2 2 3
出力例2
3
入力例3
3 2 2 1 3 1 2
出力例3
2