题目描述

描述：设 $p_1$，$p_2$，$\dots$，$p_n$ 为平面上的 $n$ 个点。我们有 $m$ 条形式为 $p_i \text{ rel } p_j$ 的规则，每条规则都告诉我们，$\text{rel}$ 关系在平面上点 $p_i$ 和 $p_j$ 的位置之间成立。例如，“$p_i \text{ NE } p_j$” 表示点 $p_j$ 位于点 $p_i$ 的东北部。有八个不同的关系 $\{\text{N, E, S, W, NE, NW, SE, SW}\}$，对应于平面上的八个方向。设 $(x_i, y_i)$ 和 $(x_j, y_j)$ 分别为 $p_i$ 和 $p_j$ 的坐标。那么 $p_i \text{ rel } p_j$ 恰好表示以下之一，具体取决于 $\text{rel}$ 的值：

• $\text{N}$ 代表北方。这意味着 $x_j = x_i$ 且 $y_j > y_i$，
• $\text{E}$ 代表东方。这意味着 $x_j > x_i$ 且 $y_j = y_i$，
• $\text{S}$ 代表南方。这意味着 $x_j = x_i$ 且 $y_j < y_i$，
• $\text{W}$ 代表西方。这意味着 $x_j < x_i$ 且 $y_j = y_i$，
• $\text{NE}$ 代表东北。这意味着 $x_j > x_i$ 且 $y_j > y_i$，
• $\text{NW}$ 代表西北。这意味着 $x_j < x_i$ 且 $y_j > y_i$，
• $\text{SE}$ 代表东南。这意味着 $x_j > x_i$ 且 $y_j < y_i$，
• $\text{SW}$ 代表西南。这意味着 $x_j < x_i$ 且 $y_j < y_i$。

问题在于确定是否可以在平面上找到 $p_1$、$p_2$、$\dots$、$p_n$，以便所有给定的规则得到满足。

输入

输入的第一行包含一个整数 $t$ ($1 \leq t \leq 20$)，这是输入中的测试用例数。每个测试用例的第一行包含两个整数 $n$ ($2 \leq n \leq 500$) 和规则数 $m$ ($1 \leq m \leq 10000$)。在以下每一 $m$ 行中，都有一个形式为 $i \text{ rel } j$ 的规则，这意味着 $p_i$ 与 $p_j$ 具有关系 $\text{rel}$。

输出

输出包含每个测试用例的一行，其中包含一个单词 $\text{POSSIBLE}$ 或 $\text{IMPOSSIBLE}$，指示测试用例中的点集是否可以根据给定规则位于平面上。

输入数据

1
2 3
2 1 N
2 2 N
1 6 6
1 E 2
1 E 3
2 N 3
4 NW 3
5 SW 4
6 NE 5

输出数据

1
IMPOSSIBLE
POSSIBLE

源于

德黑兰 2004 [Tehran]