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₂.

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

Print friendly version