The Witcher

위쳐가 큰일을 겪고 있다! 다가오는 여행을 위해 주머니 지도를 준비해야 한다. 그는 지금 선술집에 있고, 여기에는 대륙 전체의 지도가 있다. 단순화를 위해 지도는 루프가 없는 무향 그래프라고 하자. 다만 같은 두 노드 사이에 여러 간선이 있을 수 있다. 위쳐의 세계에는 주머니 지도에 넣는 모든 그래프가 다음 조건을 만족해야 한다는 불문율이 있다. 모든 정점의 차수가 짝수여야 한다. 위쳐는 이 규칙을 어기고 싶지 않고, 주머니 지도의 그래프는 선술집 지도의 그래프와 같은 노드 집합을 가져야 하며, 그 간선들은 선술집 지도의 간선들의 부분집합이어야 한다. 물론 다가오는 모험을 완수하기 위해 반드시 필요한 간선도 있으므로, 그것들도 주머니 지도에 넣고 싶어 한다. 위쳐는 주어진 조건을 만족하는 올바른 그래프를 만들 수 있는지 알고 싶어 하고, 만들 수 있다면 어떤 간선들을 주머니 지도에 넣어야 하는지 알려 주어야 한다.

첫 번째 줄에 정수 $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$를 출력해야 하며, $y\_i \geq 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\}$