SP6827 LMCONSTR - Last Minute Construction

题目描述

世界足球锦标赛决赛即将在南非举行。 为了到达体育馆,有很多小路连接着遍布全山的许多小村庄,每两个村庄之间修建了一条道路。 由于粉丝的数量将超过小山路的容量,因此组委会只有一个选择:提高在其中一个地点到达山的可能性。 但麻烦的是,如果建筑不止一次打扰一个村庄,村民将会破坏总决赛。所以组委会决定创建一些替代路线来转移一些交通。 工程师们已经确定了许多可能的地点,所有这些地点都提供了一个很好的着陆点,可以让巨型钻机飞到这里,也有一个起飞点可以把钻机从那里运回来。但由于钻头很老,它必须遵循岩石中的自然结构,因此只能用于在给定方向上钻孔。 工程师需要你使用现有道路和钻新隧道确定从着陆平台到起飞点的路线存在的地点,你最多访问每个村庄一次。 此外,一条有效的路由需要包含工程师确定的所有必要隧道,并且不应包含其他隧道。

输入格式

第一行,三个数字 $N,M,T$ 将指定村庄的数量,以及要遵循的结构和隧道。 第二行分别指定着陆平台和起飞地点的位置。 在这 $M$ 行之后,每行给出一对村庄 $a,b$ ($a \neq b$) 表示 $a$ 和 $b$ 之间的道路,可以双向使用。 最后是 $T$ 行,每行给出一对村庄 $a,b$ ($a \neq b$),表示从 $a$ 到 $b$ 需要一条隧道。隧道必须沿从 $a$ 到 $b$ 的方向钻孔。

输出格式

对于每一组数据,输出一行。 如果不可能,输出 IMPOSSIBLE ,否则输出 POSSIBLE 。 translated by [yizhixiaoyun](https://www.luogu.com.cn/user/590864)