Polish version    English version  
  History of OI


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
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 K1 and K2, can be combined in either one of the following ways:

  • by choosing all the cells from both K1 and K2, and all the connections from both K1 and K2,
  • by choosing all the cells from both K1 and K2, all the connections from both K1 and K2, and setting further connections: each cell from K1 is connected to every cell from K2.
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



Print friendly version