题目描述

在一个养老院里，$n$ 位老人正在看电视。这个电视节目由 $m$ 个频道组成，数字从 $1$ 到 $m$ 不等。每个老人都有自己喜欢和讨厌的电视频道。

如果电视正在播放某个老人讨厌的频道，他会站起来，慢慢走向电视机，把频道换成他最喜欢的，然后回到舒适的椅子上。如果有多个老人讨厌现在的频道，他们中最年轻的会站起来，把频道换成他最喜欢的，其余的人都会坐着。

当然，在一次更换频道后，另一位老人可能会觉得新频道无法忍受，所以他会更换该频道。鉴于老人们很顽固，这种情况可能会无限期地持续下去。

对于老人们最喜欢和讨厌的频道以及电视上的初始频道，确定老人们保持快乐所需的频道更改次数。

输入格式

输入的第一行包含三个整数 $n,m$ 和 $p$，分别表示养老院里老人的数量， 电视频道的数量和在电视上显示的初始频道。

以下 $n$ 行中的每一行都包含两个整数 $a_i$ 和 $b_i$，分别表示每个老人最喜欢和最讨厌的频道。

老人的输入顺序是按年龄从小到大排列的。

输出格式

仅一行，输出必须包含所需的频道更改数。如果更改无限期地继续，则输出 -1。

3 4 2
1 2
2 3
3 2

1

3 3 1
1 2
2 3
3 1

-1

4 5 2
1 3
2 3
3 2
5 1

3

提示

样例输入输出 1 解释

最初，电视上是 $2$ 频道。这个频道惹恼了最年轻和最年长的老人，所以最年轻的人站起来，把频道他最喜欢的改成 $1$ 频道，这样每个人都可以一起看 $1$ 频道。

数据规模与约定

• 对于 $50\%$ 的数据，保证 $1\le n,m\le 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n,m\le 10^5$，$1\le p\le m$，$1\le a_i, b_i\le m$，$a_i \neq b_i$。