COCI '14 Contest 3 #2 Dom

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.45s
Memory limit: 32M

Problem type

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.

Input Specification

The first line of input contains three integers N, M and P (1 \le N, M \le 10^5, 1 \le P \le 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 a_i and b_i (1 \le a_i, b_i \le M, a_i \ne b_i), the favourite and hated channel of each pensioner.

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

Output Specification

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


In test cases worth 50% of total points, it will hold 1 \le N, M \le 10^3.

Sample Input 1

3 4 2
1 2
2 3
3 2

Sample Output 1


Explanation for Sample Output 1

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.

Sample Input 2

3 3 1
1 2
2 3
3 1

Sample Output 2


Sample Input 3

4 5 2
1 3
2 3
3 2
5 1

Sample Output 3



There are no comments at the moment.