Sightseeing Tour

Time limit1sMemory limit128 MB

Summary

Decide whether a mixed graph of one-way and two-way streets has a closed tour that uses every street exactly once starting and ending at the same junction.

Level: Medium7 of 10
Topics: Graph, Union-find, DFS, Implementation
Solved: No attempts yet

Problem

The city council wants to run a sightseeing bus tour through the city so that tourists can see every corner of it. The tour must be planned so that every street is driven along exactly once, and the bus must start and finish at the same junction. Streets are either one-way or two-way, and the tour bus must obey these traffic rules. Determine whether such a sightseeing tour can be constructed.

Input

The first line contains a single positive integer $n$ , the number of test scenarios.

Each scenario begins with a line containing two positive integers $m$ and $s$ ( $1 \le m \le 200$ , $1 \le s \le 1000$ ): the number of junctions and the number of streets.

Each of the next $s$ lines describes one street with three integers $x_i$ , $y_i$ , and $d_i$ ( $1 \le x_i, y_i \le m$ , $0 \le d_i \le 1$ ), where $x_i$ and $y_i$ are the junctions joined by the street. If $d_i = 1$ the street is one-way (from $x_i$ to $y_i$ ); otherwise it is two-way. You may assume there is a junction from which every other junction can be reached.

Output

For each scenario, output a single line containing possible if a sightseeing tour can be constructed, or impossible otherwise.

Examples3

Example 1

Input

Expected output

possible
impossible
impossible
possible

Example 2
Input
```
1
1 1
1 1 0
```
Expected output
```
possible
```
Example 3
Input
```
1
2 1
1 2 0
```
Expected output
```
impossible
```