Chochlik

In a nineteenth-century factory, power was transmitted through drive belts. The factory ran smoothly until one day a mischievous imp slipped inside and swapped the arrangement of some of the belts. The owner now wants to know whether, with the belts in their current arrangement, the factory can still work correctly.

There are two ways to connect two distinct wheels. If a wheel spins in some direction, a wheel joined to it by a type-$A$ connection spins in the same direction, while a wheel joined by a type-$B$ connection spins in the opposite direction.

The two ways of connecting wheels with drive belts.

A department of the factory can work correctly if setting any single wheel spinning never forces some other wheel to turn in two opposite directions at the same time.

Your task is to write a program that, for each department, decides whether it can work correctly with the belts arranged as they are now.

The first line of standard input contains one integer $d$ ($1 \le d \le 10$), the number of departments in the factory.

The descriptions of the departments follow. The first line of each description contains two integers $k$ and $p$ ($1 \le k \le 100\,000$, $0 \le p \le 100\,000$): the number of wheels in the department and the number of connections between them. Each of the next $p$ lines contains two integers $a_i$ and $b_i$ and one letter $c_i$, separated by single spaces ($1 \le a_i, b_i \le k$, $c_i \in \{A, B\}$, $a_i \ne b_i$), giving the numbers of the two connected wheels and the type of connection between them.

Two wheels may be joined by more than one belt.

Print exactly $d$ lines to standard output. The $i$-th line should contain one word:

• TAK if the $i$-th department can work correctly
• NIE otherwise

Explanation of the sample. The first department cannot work correctly: spinning wheel $1$ clockwise would force wheel $2$ to turn clockwise and counterclockwise at the same time, which is not allowed. The second department has no belts at all, so it is a valid configuration.