Last Minute Constructions

The final of the upcoming soccer world championship will be held in South Africa. To give the event extra prestige, the organising committee decided to hold the final on a plateau of Mafadi, the highest mountain in South Africa. During the preparations, however, the logistics of such a huge event were badly underestimated.

With barely a month to go, the stadium on the plateau is finished, but there is almost no way to bring people up to it. So far there are only small roads connecting the many little villages scattered across the mountain. Moreover, the efficient builders of old only ever built a road between two villages when no connection between them existed yet. As a result, the roads never form a cycle; altogether they form a forest.

Since the crowds far exceed the capacity of the narrow mountain roads, the committee wants to improve access to the mountain at one site. Using an old tunnel-drill, it plans to create a number of alternative routes (tunnels) to divert some of the traffic.

The engineers have identified several candidate sites. Each site comes with a landing platform, where the drill is flown in, and a takeoff spot, from which it is flown back. Because the drill is very old, it must follow the natural rock structure and can only drill in the given direction.

For each candidate site, decide whether there is a route for the drill, using existing roads and newly drilled tunnels, from the landing platform to the takeoff spot such that:

• every village is visited at most once;
• the route contains all the tunnels the engineers deemed necessary; and
• the route contains no other tunnels.

Each necessary tunnel must be traversed in its given direction.

The first line contains the number of test cases.

Each test case starts with a line containing three integers $N$, $M$, $T$ ($1 \le N, M \le 100,000$, $0 \le T \le 100,000$): the number of villages, the number of existing roads, and the number of tunnels that must be drilled.

The second line gives the location of the landing platform and of the takeoff spot, in that order (the two are different).

The next $M$ lines each contain two villages $a$ and $b$ ($0 \le a, b < N$, $a \ne b$), describing an existing road between $a$ and $b$ that can be used in both directions.

Finally, $T$ lines each contain two villages $a$ and $b$ ($0 \le a, b < N$, $a \ne b$), describing a necessary tunnel that must be drilled in the direction from $a$ to $b$.

Villages are numbered from $0$ to $N-1$.

For each test case, print a single line containing "POSSIBLE" if the construction can be carried out under the given restrictions, or "IMPOSSIBLE" otherwise.