猎魔人现在遇到了大麻烦！他需要为即将到来的旅程准备一张口袋地图。他现在在一家酒馆里，这里有一幅整个大陆的地图。为了简单起见，我们假设这幅地图只是一个无自环的无向图，但它可能在同一对节点之间包含多条重边。在猎魔人的世界里有一个不成文的规定，放入口袋地图的每个图都必须满足以下条件：每个顶点的度数都必须是偶数。猎魔人不想打破这个规定，而且口袋地图中的图应该与酒馆地图中的图具有相同的节点集，且该图的边集应该是酒馆地图中图的边集的子集。当然，有一些边是猎魔人完成即将到来的冒险所必需的，因此他也希望将它们放入他的口袋地图中。猎魔人想知道，他是否能构建一个满足给定条件的合法图，如果可以，你应该告诉他应该将哪些边放入他的口袋地图中。

输入格式

第一行包含一个整数 $Z \le 100$，表示接下来描述的测试用例数量。

每个测试用例的第一行包含两个整数 $n, m$，分别表示酒馆地图中图的节点数和边数。

接下来的 $m$ 行中，每行包含一条边的描述。第 $i$ 行包含三个整数 $a_i, b_i, x_i$，表示第 $i$ 条边连接编号为 $a_i$ 和 $b_i$ 的节点。如果 $x_i = 1$，则表示猎魔人的口袋地图中必须包含这条边；否则你可以选择是否包含它，但不是必须的。

输出格式

对于每个测试用例，如果猎魔人可以准备满足所有条件的口袋地图，则第一行应输出单词 TAK，否则输出 NIE。

如果第一行包含单词 TAK，则在接下来的 $m$ 行中，你应该每行输出一个数字 $y_i \in \{0, 1\}$，使得 $y_i \ge x_i$，且由 $y_i = 1$ 的边构成的图满足猎魔人的所有条件。

数据范围

• $n \in [1, 5 \cdot 10^5]$
• $m \in [0, 5 \cdot 10^5]$
• $a_i, b_i \in [1, n]$，且 $a_i \neq b_i$
• $x_i \in \{0, 1\}$
• $Z \le 100$

样例

样例输入 1

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

样例输出 1

TAK
1
0
0
1
1
NIE