2865 - 看电影

题目描述

C 的学校组织同学们看电影,为了满足同学们不同的观影爱好,贴心的为每位同学发放了一张神奇的电影票,这张票的神奇之处是可以用 2 次,正面和反面各有一场电影(本题使用不同的数字编号代表不同的电影)。

除了小 C 以外,有 N 名同学领到了电影票,同学们的编号依次为 1 \sim N。第 i 位同学领到的神奇电影票的正面是该同学最想看的电影,编号为 A_i;反面是影院推荐的另一场热门电影,编号为 B_i,正反面没有使用顺序的限制,既可以先看正面的电影,也可以先看反面的电影。

C 领到票后发现,只有他的电影票正面和反面的电影,都不是自己最想看的电影。于是他想到了通过交换的方式来换到自己最想看电影的电影票。

如果小 C 票的一面有另一位同学最喜欢看的电影,那么另一位同学也会愿意和小 C 交换。

请问小 C 最少要交换多少次,才能换到带有自己最喜欢电影的电影票。

输入

1 行读入一个整数 N,表示除了小 C 以外,领到电影票的同学的数量,这些同学依次从 1 \sim N 编号。

接下来 N 行,依次读入每位同学电影票正、反面的电影编号 A_iB_i ,两个数用空格隔开。

最后一行,依次读入三个整数 M,X,Y ,分别表示小 C 最喜欢的电影编号,以及小 C 拿到电影票的正面电影和反面电影的编号。

输出

输出小 C 的最少交换次数;

请注意,如果小 C 同学无法交换到自己最喜欢电影的电影票,请输出 IMPOSSIBLE

样例

输入

4
8 5
5 4
7 4
1 5
4 1 8

输出

2

输入

5
1 2
3 6
5 2
0 7
9 1
2 8 0

输出

IMPOSSIBLE
说明

样例 1 解释

除了小 C 另外有 4 名同学领到了电影票。

C 同学最喜欢编号为 4 的电影,但他拿到电影票的正反面分别是编号为 1 和 编号为 8 的电影。

他会先和第 4 名同学交换,得到一张正、反面分别是 15 的电影,再拿这张票和第 2 名同学交换,就得到了含有自己最喜欢的编号为 4 的电影的电影票。

他也可以先和第 1 名同学交换,再和第 2 名同学交换,这和上一种交换方式的交换次数是一样的。

数据范围

对于 100\% 的数据,1 \le N \le 10000 \le A_i,B_i,M,X,Y \le 10^9

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 293
通过人数 114
金币数量 2 枚
难度 基础


上一题 下一题