XI Olympiad in Informatics 2003/2004
|
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:
Write a programme that:
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.
k lines should be written to the standard ouput. In the ith line one word should be written: