시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 7 6 6 85.714%

문제

In a retirement home, N senior citizens are watching television. The television programme consists of M channels denoted with numbers from 1 to M. Each of the pensioners has their own favourite and hated TV channel.

If the television is currently displaying the hated channel of a certain pensioner, he will get up, slowly walk over to the TV set and change the channel to his favourite and get back to his comfortable chair. If there are multiple pensioners who hate the current channel, the youngest of them will get up (he’s young, he doesn’t mind) and the rest will remain seated.

Of course, after one change of channel, it is possible that another pensioner finds the new channel intolerable so he will change that channel. Given the fact that the pensioners are stubborn, this may continue indefinitely.

For the pensioners’ favourite and hated channels and the initial channel on TV, determine the number of channel changes it takes for the pensioners to remain happy and seated.

입력

The first line of input contains three integers N, M and P (1 ≤ N, M ≤ 105, 1 ≤ P ≤ M), the number of pensioners, the number of TV channels and the initial channel displayed on TV.

Each of the following N lines contains two integers ai and bi (1 ≤ ai, bi ≤ M, ai ≠ bi), the favourite and hated channel of each pensioner.

The ordering of pensioners in the input is from the youngest to the oldest.

출력

The first and only line of output must contain the required number of channel changes. If the changes continue indefinitely, output -1.

예제 입력

3 4 2
1 2
2 3
3 2

예제 출력

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

힌트

Clarification of the first example: Initially, channel 2 was on TV. This channel annoys the youngest and the oldest pensioner, so the youngest gets up enthusiastically and changes the channel so everyone can watch channel 1 together.