Elderly TV Channel Change

In a nursing home, n seniors are watching TV. The TV offers m channels numbered from 1 to m. Each senior has a favorite channel and a channel he dislikes. At any moment, if the TV displays a channel that some senior dislikes, that senior will act. If multiple seniors dislike the current channel, the youngest (i.e. the one with the highest index) will stand up, change the channel to his favorite, and then return to his seat. This change may cause another senior to dislike the new channel, triggering another change, and so on.

The process continues until no senior dislikes the channel being shown. It is possible that the changes continue indefinitely. Given the favorite and hated channels for each senior and the initial channel on TV, determine the number of channel changes needed for the seniors to remain happy. If the channel changes occur indefinitely, output -1.

The process is defined by the following transition: Let the current channel be c. If there is at least one senior such that his hated channel equals c, let i be the maximum index (representing the youngest among those) with hated[i] = c, and change the channel to favorite[i]. Each such switch is counted as one change. The process stops when no senior dislikes the current channel or if a cycle is detected, in which case the answer is -1.

Note: Seniors are numbered 1 through n. Assume that the input order is from oldest to youngest (i.e. senior n is the youngest).

inputFormat

The first line contains three integers n, m, and initial representing the number of seniors, the number of TV channels, and the initial channel on TV respectively.

Then follow n lines. The i-th line (for 1 ≤ i ≤ n) contains two integers favorite[i] and hated[i] which represent the favorite channel and the hated channel of the i-th senior.

outputFormat

Output a single integer denoting the number of channel changes needed so that no senior dislikes the current channel. If the channel changes continue indefinitely, output -1.

sample

2 3 1
2 3
3 2

0