N명의 아이들이 집에서 TV를 본다. TV에서 나오는 프로그램은 총 M개이고, 각각 1~M번 채널에서 방영한다. 아이들은 각자 가장 좋아하는 프로그램과 가장 싫어하는 프로그램을 하나씩 갖고 있다.

만약 TV에서 나오는 프로그램을 어떤 아이가 싫어한다면, 그 아이는 리모컨을 이용해서 가장 좋아하는 프로그램으로 채널을 돌린다. 만약 TV에 나오는 프로그램을 싫어하는 아이가 여러 명이라면, 가장 어린 아이가 리모컨을 잡는다.

한 명의 아이가 채널을 돌린 후라도, 다른 아이가 또 채널을 돌릴 수 있다. 이런 식으로 아이들이 채널을 돌리면, 특정 채널로 돌린 이후에는 더 이상 리모컨을 잡는 아이가 없거나 같은 상황이 무한히 반복될 것이다.

아이들의 프로그램 선호 정보가 주어질 때 몇 명의 아이가 채널을 돌리는지 구하는 프로그램을 작성하여라.

입력 형식

• 첫 번째 줄에는 아이의 수 N, 채널의 수 M, TV의 처음 상태 P가 주어진다. (1 ≤ N, M ≤ 100,000, 1 ≤ P ≤ M)
• 두 번째 줄부터 N개의 줄에는 각 아이가 가장 좋아하는 채널의 번호 A와 가장 싫어하는 채널의 번호 B가 주어진다. (1 ≤ A, B ≤ M) 입력은 나이순으로 주어진다. 즉, 두 번째 줄의 정보는 가장 어린 아이의 정보이며 마지막 줄의 정보는 가장 늙은 아이의 정보이다.

출력 형식

입출력 예

입력

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 설명

처음에는 TV에서 채널 2가 나온다. 이 채널은 1, 3번째 아이가 싫어하는데, 1번 아이가 가장 어리므로 1번 아이가 채널 1로 바꾼다. 채널 1을 싫어하는 아이는 없기 때문에 더 이상의 채널 변경은 없다.

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 <= 10^5 , 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.

출력

입출력 예

입력

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

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.

출처:coci 2013/2014 2/6
번역:functionx