Description

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

If the TV is showing a channel that an elderly person hates, they will stand up, slowly walk to the TV, change the channel to their favorite one, and then return to their comfortable chair. If multiple elderly people hate the current channel, the youngest among them will stand up and change the channel to their favorite, while everyone else stays seated.

Of course, after one channel change, another person may find the new channel unbearable, so they will change it again. Since the elderly people are stubborn, this may continue forever.

Given the favorite and hated channels of all elderly people, and the initial channel on the TV, determine how many channel changes are needed for everyone to stay happy.

Input Format

The first line 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 shown on the TV.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$, representing the favorite channel and the hated channel of each elderly person.

The elderly people are given in input order from youngest to oldest.

Output Format

Output one line containing the required number of channel changes. If the changes continue forever, output -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

Hint

Explanation of Sample Input/Output 1

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

Constraints

• For $50\%$ of the testdata, it is guaranteed that $1\le n,m\le 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1\le n,m\le 10^5$, $1\le p\le m$, $1\le a_i, b_i\le m$, and $a_i \neq b_i$.

Translated by ChatGPT 5