점 배치

평면 위에 $n$개의 점 $p_1, p_2, \ldots, p_n$이 있다. 점 $p_i$의 좌표를 $(x_i, y_i)$라고 하자. $p_i \; rel \; p_j$ 형태의 규칙 $m$개가 주어지며, 각 규칙은 점 $p_i$와 점 $p_j$의 상대적 위치 관계 $rel$을 나타낸다. 예를 들어 "$p_i$ NE $p_j$"는 점 $p_j$가 점 $p_i$의 북동쪽(NorthEast)에 있음을 의미한다.

관계 $rel$은 평면의 여덟 방향에 대응하는 여덟 종류 $\{N, E, S, W, NE, NW, SE, SW\}$ 중 하나이며, $rel$의 값에 따라 $p_i \; rel \; p_j$는 정확히 다음 중 하나를 의미한다.

1. N (북, North): $x_j = x_i$이고 $y_j > y_i$
2. E (동, East): $x_j > x_i$이고 $y_j = y_i$
3. S (남, South): $x_j = x_i$이고 $y_j < y_i$
4. W (서, West): $x_j < x_i$이고 $y_j = y_i$
5. NE (북동, NorthEast): $x_j > x_i$이고 $y_j > y_i$
6. NW (북서, NorthWest): $x_j < x_i$이고 $y_j > y_i$
7. SE (남동, SouthEast): $x_j > x_i$이고 $y_j < y_i$
8. SW (남서, SouthWest): $x_j < x_i$이고 $y_j < y_i$

주어진 모든 규칙을 만족하도록 점 $p_1, p_2, \ldots, p_n$을 평면 위에 배치하는 것이 가능한지 판별하여라.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 20$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 점의 개수 $n$ ($2 \le n \le 500$)과 규칙의 개수 $m$ ($1 \le m \le 10^4$)이 주어진다. 이어지는 $m$개의 줄에는 각각 $i \; rel \; j$ 형태의 규칙이 하나씩 주어지며, 이는 점 $p_i$가 점 $p_j$와 관계 $rel$을 가짐을 의미한다.

각 테스트 케이스마다 한 줄씩, 주어진 규칙에 따라 점들을 평면 위에 배치할 수 있으면 POSSIBLE을, 그렇지 않으면 IMPOSSIBLE을 출력한다.