Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PZPI2 - Cudowne lody

Pewnego upalnego dnia do miasteczka, w którym mieszkał Jasio, przyjechały tajemnicze samochody z ofertą sprzedaży nowych cudownych lodów. Kto tylko raz spróbował owych lodów posiadł natychmiast rzadką do tej pory umiejętność rozwiązywania trudnych zadań matematycznych. Ponieważ wszyscy chcieli zostać matematykami, ustawiały sie gigantyczne kolejki i tu i ówdzie lodów zaczynało brakować. Władze miasteczka postanowiły zaprowadzić porządek i ustaliły co następuje:

  • na każdym skrzyżowaniu będą sprzedawane lody,
  • mieszkańcy każdej ulicy muszą wspólnie ustalić, do którego skrzyżowania się udadzą,
  • mieszkańcy z dokładnie połowy ulic sąsiednich do danego skrzyżowania muszą się przy nim zebrać.

Pomóż mieszkańcom miasta podjąć decyzję, na których skrzyżowaniach, mieszkańcy których ulic mają się zebrać.

Wejście

W pierwszej linii podana jest liczba zestawów t (t <= 10). Opis każdego zestawu rozpoczyna się od podania w pierwszej linii liczby miejsc (skrzyżowań), z których będą sprzedawane lody, n <= 5000 oraz połowy liczby ulic przylegających do każdego skrzyżowania (dla wszystkich skrzyżowań identyczna liczba) k < 100. Następnie w n*k kolejnych liniach podane zostały ulice identyfikowane przez ograniczające je skrzyżowania.

Wyjście

Dla i-tego zestawu, jeżeli nie jest możliwe przydzielenie mieszkańców do skrzyżowań, wydrukuj na wyjście napis:"zestaw i N". Jeżeli natomiast jest możliwe ustawienie mieszkańców zgodne z zasadami, wypisz "zestaw i T", w linijce j podaj dokładnie k liczb całkowitych oznaczających drugie końce wybranych ulic.

Przykład

Wejście:
2
4 1
1 2
2 3
3 4
4 1
8 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 5
5 2
2 6
6 1
3 7
7 4
4 8
8 3
8 1

Wyjście:
zestaw 1 T
2
3
4
1
zestaw 2 T
5 6
1 6
2 8
3 8
2 4
5 7
3 4
1 7

Dodane przez:mima
Data dodania:2005-05-20
Limit czasu wykonania programu:20s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.