Song List

Given a list of songs, calculate the minimal number of keys a user has to press to move the cursor from a certain song to another.

There are 3 keys with different functions: "previous", "next" and "sort". When the "previous" key is pressed, the cursor moves to the previous song, if it's already at the first song, it goes to the last one. The "next" key works analogously. When the "sort" key is pressed, the list is sorted alphabetically. Each song has it's title and author, if the "sort" key is pressed when the list is sorted by title, it sorts the list by author, and vice versa. After sorting, the cursor stays at the same song.

Input

The input contains several cases. Each case begins with three positive integers: n, the number of songs(at most 10000), s and f, the initial and final position of the cursor(1 <= s, f <= n). Then n lines follow, each contains two strings with no more than 10 characters each, which are the title and the author of that song. The titles and authors are unique. Songs are initially sorted by title.

Output

For each case,output the minimal number of keys one has to press to move the cursor from its initial position to the final position.

Sample Input

6 1 4
a a
b c
c d
d b
e e
f f

Sample Output

2

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐