描述

隆德市的执行委员会想要规划一条观光巴士路线，以便游客能够看到这座美丽城市的每一个角落。他们希望构建的路线能使城市的每条街道都恰好被访问一次，并且巴士应从同一个路口出发并回到该路口。和在任何城市一样，街道要么是单向的，要么是双向的，观光巴士必须遵守交通规则。请帮助执行委员会判断在这些约束条件下是否有可能构建这样的观光路线。

输入

输入的第一行是一个正整数$n$，表示接下来测试场景的数量。每个场景的第一行包含两个正整数$m$和$s$，其中$1 \leq m \leq 200$，$1 \leq s \leq 1000$，$m$表示路口数量，$s$表示街道数量。接下来的$s$行描述街道信息。每行包含三个整数$x_i$，$y_i$和$d_i$，其中$1 \leq x_i, y_i \leq m$，$0 \leq d_i \leq 1$，$x_i$和$y_i$是由街道连接的路口。如果$d_i = 1$，则该街道是单向街道（从$x_i$到$y_i$），否则是双向街道。你可以假设存在一个可以到达所有其他路口的路口。

输出

对于每个场景，输出一行，包含文本“possible”或“impossible”，表示在给定的约束条件下是否有可能构建观光路线。

输入数据 1

4
5 8
2 1 0
1 3 0
4 1 1
1 5 0
5 4 1
3 4 0
4 2 1
2 2 0
4 4
1 2 1
2 3 0
3 4 0
1 4 1
3 3
1 2 0
2 3 0
3 2 0
3 4
1 2 0
2 3 1
1 2 0
3 2 0

输出数据 1

possible
impossible
impossible
possible

来源

2003年西北欧竞赛