Olimpiada Informatyczna

XI Olympiad in Informatics 2003/2004

Task: KAG

C-algae

III stage competition (national finals)

Source file: kag.*

Memory limit:

32 MB

C-algae is the Byteotians' favourite dish of their national cuisine. C-algae have a very specific structure. An algae consisting of a single cell is a c-algae. Two c-algae K₁ and K₂, can be combined in either one of the following ways:

by choosing all the cells from both K₁ and K₂, and all the connections from both K₁ and K₂,
by choosing all the cells from both K₁ and K₂, all the connections from both K₁ and K₂, and setting further connections: each cell from K₁ is connected to every cell from K₂.

As a result we obtain a new c-algae K.
Unfortunately the hostile country of Bitotia has recently started selling algae imitating c-algae. These look so alike that it is hard to tell the difference between a false one and a genuine c-algae. This is the reason why the Byteotian government has asked you to write a programme that would allow verification if a given algae is a c-algae.

Task

Write a programme that:

reads the descriptions of algae from the standard input,
checks which of them are proper c-algae,
writes the answer to the standard output.

Input

In the first line of the standard input a single integer k is written, 1 <= k <= 10, it denotes the number of algae to be examined. Descriptions of k algae are written in the following lines. Each single description is of the following form: in the first line there are two integers written, separated by a single space, n i m, 1 <= n <= 10.000, 0 <= m <= 100.000. They denote the number of cells and the number of connections respectively. The cells are numbered from 1 to n. In the following m lines the connections are described - each by two integers a, b, separated by a single space (a<>b, 1 <= a,b <= n), indicating that the cells a and b are connected. Each connection is specified once.

Output

k lines should be written to the standard ouput. In the ith line one word should be written:

TAK - ('yes' in Polish) - if the ith algae is a proper c-algae,
NIE - ('no' in Polish) - otherwise