Last Minute Constructions

For the upcoming soccer world championship’s finals in South Africa the organisation committee has planned a very prestigious project. To take the two teams, which are battling it out for the title, to new heights, the final should take place on a plateau of the “Mafadi”, the highest mountain of South Africa. During the preparations, the logistics of such a huge event have been severely underestimated.

Now, with barely a month to go, the stadium on top of the plateau is finished but the means of transportation to the plateau are next to nonexistent. Until now, there are only small roads connecting many little villages spread all over the mountain. Furthermore, known for their efficiency, ancient South African builders only built a road between two villages, if no other connection existed so far.

Since the amount of fans would exceed the capacity of the small mountain roads, this leaves the committee with only one choice: improve the possibilities to reach the mountain at one of the sites. But as if this wasn’t enough trouble to go through, the mountain folks have announced to sabotage the finals, if the constructions would disturb any village more than once. Since the committee has access to an old tunnel-drill, it has decided to create a number of alternative routes to divert a bit of the traffic.

The engineers have identified a number of possible sites, all offering a good landing spot to fly in the giant drill to and a takeoff spot to transport the drill back from. But as the drill is really old, it has to follow the natural structures in the rock and can therefore only be used to drill in the given direction. Thus, the engineers seek your help to identify the sites on which a route for the drill (using existing roads and drilling new tunnels) exists from the landing platform to the takeoff spot, visiting each village at most once. Furthermore, a valid route needs to contain all the tunnels identified necessary by the engineers, and it should contain no other tunnels.

The input to your program provided by the South African building committee will be structured as follows. Each input file begins with the number of test cases on a single line. On the first line of every test case three numbers N, M, T (1 ≤ N, M ≤ 100 000, 0 ≤ T ≤ 100 000) will specify the number of villages, as well as connections and tunnels to follow. The second line specifies the location of the landing platform and the takeoff spot respectively (landing platform ≠ takeoff spot). After this M lines follow, each giving a pair of villages a b (0 ≤ a, b < N, a ≠ b) to indicate an existing road between a and b which can be used in both directions. Finally T lines follow, each giving a pair of villages a b (0 ≤ a, b < N, a ≠ b) to indicate that a tunnel was deemed necessary for the finals from a to b. The tunnel has to be drilled in the direction from a to b.

For each of the presented test cases, print a single line containing either “IMPOSSIBLE” whenever the construction is not possible, or “POSSIBLE” whenever the constructions can be carried out under the given restrictions.