在一个养老院里，有 $N$ 位老人正在看电视。电视节目有 $M$ 个频道，用 $1$ 到 $M$ 的整数表示。每位老人都有自己最喜欢的频道和最讨厌的频道。

如果电视当前播放的是某位老人最讨厌的频道，他就会站起来，慢慢走到电视机前，把频道换成他最喜欢的频道，然后回到他舒服的椅子上。如果有多个老人讨厌当前的频道，其中最年轻的那位会站起来去换台（他年轻，他不介意），而其他人则保持坐姿。

当然，在一次换台之后，可能会有另一位老人发现新频道无法忍受，从而去换台。鉴于老人们都很固执，这种情况可能会无限持续下去。

已知每位老人最喜欢和最讨厌的频道，以及电视的初始频道，请计算需要进行多少次换台，才能让所有老人都感到满意并保持坐姿。

输入格式

输入的第一行包含三个整数 $N$、$M$ 和 $P$（$1 \le N, M \le 10^5$，$1 \le P \le M$），分别表示老人的数量、电视频道的数量以及电视的初始频道。

接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le M$，$a_i \neq b_i$），分别表示每位老人最喜欢和最讨厌的频道。

输入中老人的顺序是从最年轻的到最年长的。

输出格式

输出的第一行也是唯一的一行，应当包含所需的换台次数。如果换台过程无限持续下去，则输出 -1。

子任务

对于占总分 $50\%$ 的测试数据，满足 $1 \le N, M \le 10^3$。

样例

输入样例 1

3 4 2
1 2
2 3
3 2

输出样例 1

1

输入样例 2

3 3 1
1 2
2 3
3 1

输出样例 2

-1

输入样例 3

4 5 2
1 3
2 3
3 2
5 1

输出样例 3

3

说明

样例 1 说明：最初，电视播放的是频道 2。这个频道让最年轻和最年长的老人都感到厌烦，因此最年轻的老人兴致勃勃地站起来换台，这样大家就可以一起看频道 1 了。