Polish version    English version  
  Historia OI -> XI OI 2003/2004


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia 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
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
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
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: KAG

Kaglony

Zawody III stopnia  
Plik źródłowy: kag.*
Limit pamięci: 32 MB

Kaglony to narodowa ulubiona potrawa mieszkańców Bajtocji. Kaglony mają bardzo charakterystyczną budowę. Glon składający się z jednej komórki jest kaglonem. Mając dwa kaglony K1 i K2, można je połączyć w następujący sposób:

  • biorąc wszystkie komórki z K1 i K2, oraz wszystkie połączenia z K1 i K2,
  • biorąc wszystkie komórki z K1 i K2, wszystkie połączenia z K1 i K2, oraz dodając nowe połączenia: każdą komórkę z K1 łączymy z każdą komórką z K2.
Otrzymujemy w wyniku nowy kaglon K.
Niestety niedawno wrogie państwo Bitocji rozpoczęło sprzedaż glonów imitujących kaglony. Glony te są na tyle podobne że na pierwszy rzut oka trudno odróżnić je od oryginału, dlatego też rząd Bajtocji poprosił Cię o napisanie programu, który umożliwiłby sprawdzanie czy dany glon jest kaglonem.

Zadanie

Napisz program który:

  • wczyta ze standardowego wejścia opisy glonów,
  • sprawdzi które z nich są poprawnymi kaglonami,
  • zapisze na standardowym wyjściu odpowiedź.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita k, 1 <= k <= 10, liczba badanych glonów. W kolejnych wierszach zapisane jest k opisów glonów. Pojedynczy opis ma następującą postać: w pierwszym wierszu zapisane są dwie liczby całkowite oddzielone pojedynczym odstępem n i m, 1 <= n <= 10.000, 0 <= m <= 100.000, odpowiednio liczba komórek i liczba połączeń. Komórki są ponumerowane od 1 do n. W kolejnych m wierszach opisane są połączenia, w każdym z tych wierszy zapisano dwie liczby całkowite oddzielone pojedynczym odstępem a, b, a<>b, 1 <= a,b <= n, oznaczające, że komórki a i b są połączone. Każde połączenie wymienione jest jeden raz.

Wyjście

Na standardowym wyjściu należy zapisać k wierszy. W i-tym wierszy należy zapisać jedno słowo:

  • TAK - jeśli i-ty glon jest poprawnym kaglonem,
  • NIE - wpp.



Wersja do druku