The Two-ball Game

Time limit1sMemory limit128 MB

Summary

Given n points, decide whether two non-crossing paths exist from s1 to t1 and s2 to t2 with no shared vertex.

Level: Medium7 of 10
Topics: Geometry, Graph, Shortest path
Solved: No attempts yet

Problem

The national soccer team of Lizarb is one of the favourites for the upcoming World Cup. Their greatest strengths are precise dribbling and passing: any player can pass the ball directly to any other player on the field, at any distance. The captain, Oicul, insists that a drill called the two-ball game sharpens these skills.

In the two-ball game, $n \ge 4$ players stand on the field and never move during the game. Four of them are special: two starting players $s_1$ and $s_2$ , and two terminal players $t_1$ and $t_2$ . At the start, $s_1$ holds a white ball and $s_2$ holds a black ball.

Each ball travels from player to player. A single pass is a straight line segment between two players. The aim is for the white ball to end up with $t_1$ and the black ball to end up with $t_2$ .

To avoid collisions the game has two rules:

No two ball trajectories may cross each other.
No player may touch a ball more than once. This includes the starting and terminal players.

For some placements of the players the two-ball game can be played, and for others it cannot. Write a program that decides, for a given placement, whether the two-ball game is possible.

Input

The first line contains a single integer: the number of test cases.

Each test case begins with a line containing the number of players $n$ ( $4 \le n \le 100000$ ), followed by $n$ lines giving the players' coordinates, one player per line. All coordinates are pairwise distinct, and no three players are collinear (no three lie on a single straight line).

The coordinates are listed in a fixed role order: the first is $s_1$ , the second is $t_1$ , the third is $s_2$ , the fourth is $t_2$ , and each remaining line is another player.

Output

For each test case, print a single line containing POSSIBLE if the two-ball game can be played for that placement, or IMPOSSIBLE otherwise.

Examples4

Example 1

Input

2
5
2.01 0.02
1.04 3.02
0.01 0.99
4.1 3.2
2.1 2.01
5
2.01 0.02
1.04 3.02
0.01 0.99
2.1 2.01
4.1 3.2

Expected output

IMPOSSIBLE
POSSIBLE

Example 2
Input
```
1
4
0 0
4 4
4 0
0 4
```
Expected output
```
IMPOSSIBLE
```
Example 3
Input
```
1
4
0 0
4 0
4 4
0 4
```
Expected output
```
POSSIBLE
```
Example 4
Input
```
1
4
0 0
10 0
5 9
5 3
```
Expected output
```
POSSIBLE
```