In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
King Byteasar I the Great is the ruler of a mighty and rich country of Byteland. There are towns in the country. King Byteasar would like to improve the infrastructure of Byteland and has ordered the royal architects to prepare plans for building highways across the country. He has received proposals, each of which is described by three numbers , , , where and are the towns being the endpoints of the highway, and denotes the cost of building this highway. Each highway is bidirectional and does not visit any town except for its endpoints.
The king would like to choose the highways so that there exists at least one way of travelling between any pair of towns, possibly by visiting several towns along the way. Byteasar would like to build the highway network as cheaply as possible.
Write a program which:
The first line of the input contains two integers: the number of towns, , and the number of proposed highways, , separated with a single space and satisfying the conditions: , . Each of the following lines contains three space-separated integers , , , describing the proposed highway. Here and denote the numbers of towns which are endpoints of the highway, and is the price of the highway (, ).
The output should consist of lines. The -th of those lines should contain a word "TAK" or "NIE", depending on whether there exists a highway network satisfying Byteasar's requirements containing the -th highway from the input. You can safely assume that there exists at least one highway network satisfying Byteasar's requirements.
For the input data:
6 10 1 2 2 1 6 1 1 5 3 4 1 5 2 6 2 2 3 5 4 3 4 3 5 4 4 5 4 5 6 3
the correct result is:
TAK TAK TAK NIE TAK NIE TAK TAK TAK TAK
Task author: Wojciech Smietanka.