Points

There are $n$ points $p_1, p_2, \ldots, p_n$ on the plane. Let the coordinates of point $p_i$ be $(x_i, y_i)$. You are given $m$ rules of the form $p_i \; rel \; p_j$, each stating that the relation $rel$ holds between the positions of points $p_i$ and $p_j$. For example, "$p_i$ NE $p_j$" indicates that point $p_j$ lies to the NorthEast of point $p_i$.

The relation $rel$ is one of eight kinds $\{N, E, S, W, NE, NW, SE, SW\}$, corresponding to the eight directions on the plane. Depending on the value of $rel$, $p_i \; rel \; p_j$ means exactly one of the following:

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

Determine whether it is possible to place the points $p_1, p_2, \ldots, p_n$ on the plane so that all given rules are satisfied.

The first line contains a single integer $t$ ($1 \le t \le 20$), the number of test cases. The first line of each test case contains two integers $n$ ($2 \le n \le 500$), the number of points, and $m$ ($1 \le m \le 10^4$), the number of rules. Each of the following $m$ lines contains one rule of the form $i \; rel \; j$, meaning that point $p_i$ has relation $rel$ with point $p_j$.

For each test case, print a single line containing either POSSIBLE or IMPOSSIBLE, indicating whether the points can be placed on the plane according to the given rules.