小 C 的学校组织同学们看电影,为了满足同学们不同的观影爱好,贴心的为每位同学发放了一张神奇的电影票,这张票的神奇之处是可以用 2 次,正面和反面各有一场电影(本题使用不同的数字编号代表不同的电影)。
除了小 C 以外,有 N 名同学领到了电影票,同学们的编号依次为 1 \sim N。第 i 位同学领到的神奇电影票的正面是该同学最想看的电影,编号为 A_i;反面是影院推荐的另一场热门电影,编号为 B_i,正反面没有使用顺序的限制,既可以先看正面的电影,也可以先看反面的电影。
小 C 领到票后发现,只有他的电影票正面和反面的电影,都不是自己最想看的电影。于是他想到了通过交换的方式来换到自己最想看电影的电影票。
如果小 C 票的一面有另一位同学最喜欢看的电影,那么另一位同学也会愿意和小 C 交换。
请问小 C 最少要交换多少次,才能换到带有自己最喜欢电影的电影票。
第 1 行读入一个整数 N,表示除了小 C 以外,领到电影票的同学的数量,这些同学依次从 1 \sim N 编号。
接下来 N 行,依次读入每位同学电影票正、反面的电影编号 A_i 和 B_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
除了小 C 另外有 4 名同学领到了电影票。
小 C 同学最喜欢编号为 4 的电影,但他拿到电影票的正反面分别是编号为 1 和 编号为 8 的电影。
他会先和第 4 名同学交换,得到一张正、反面分别是 1、5 的电影,再拿这张票和第 2 名同学交换,就得到了含有自己最喜欢的编号为 4 的电影的电影票。
他也可以先和第 1 名同学交换,再和第 2 名同学交换,这和上一种交换方式的交换次数是一样的。
对于 100\% 的数据,1 \le N \le 1000,0 \le A_i,B_i,M,X,Y \le 10^9。
东方博宜OJ