Problem Description

In a nursing home, $n$ elderly people are watching TV. The TV program consists of $m$ channels, numbered from $1$ to $m$. Each elderly person has their favorite and disliked TV channels.

If the TV is showing a channel that an elderly person dislikes, they will stand up, slowly walk to the TV, switch it to their favorite channel, and then return to their comfortable chair. If multiple elderly people dislike the current channel, the youngest among them will stand up and switch the channel to their favorite, while the others will remain seated.

Of course, after one channel change, another elderly person might find the new channel unbearable and will switch it again. Given the stubbornness of the elderly, this situation might continue indefinitely.

For the favorite and disliked channels of the elderly people and the initial channel on the TV, determine the number of channel changes required to keep the elderly people happy.

Input Format

The first line of input contains three integers $n$, $m$, and $p$, representing the number of elderly people in the nursing home, the number of TV channels, and the initial channel displayed on the TV, respectively.

The following $n$ lines each contain two integers $a_i$ and $b_i$, representing the favorite and disliked channels of each elderly person, respectively.

The input order of the elderly people is sorted by age from youngest to oldest.

Output Format

Output a single line containing the required number of channel changes. If the changes continue indefinitely, output -1.

Sample Input and Output

Sample Input #1

3 4 2
1 2
2 3
3 2

Sample Output #1

1

Sample Input #2

3 3 1
1 2
2 3
3 1

Sample Output #2

-1

Sample Input #3

4 5 2
1 3
2 3
3 2
5 1

Sample Output #3

3

Notes

Explanation of Sample Input and Output #1

Initially, the TV is on channel $2$. This channel annoys both the youngest and the oldest elderly person, so the youngest one stands up and switches the channel to their favorite, which is channel $1$, allowing everyone to watch channel $1$ together.

Data Size and Constraints

• For $50\%$ of the test cases, $1 \le n, m \le 10^3$.
• For $100\%$ of the test cases, $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$.

见题面 Input 部分

见题面 Output 部分