Przewody

23.11.2011

Przewody

Limit czasowy: 3000 milisekund
Limit pamięciowy: 64000 kilobajtów


Hektor niepewny swej przyszłości na rynku pracy postanowił nauczyć się konstruowania zespołów elektronicznych. W pierwszej kolejności postanowił zająć się zamykaniem obwodu elektrycznego na dwuwymiarowej płytce. Przez środek płytki przebiega linia zasilająca na której znajduje się n złączy numerowanych kolejno od 1 do n. Linia zasilająca dzieli płytkę na połowy, które będziemy nazywali dolną i górną częścią płytki. Na górnej części płytki poprowadzono przewody tak, że każdy przewód łączy dokładnie dwa złącza, żadne dwa przewody nie przecinają ani nie dotykają się i każde złącze jest podpięte do dokładnie jednego z przewodów (patrz przykłady). Przewody nie mogą też przecinać linii zasilającej.

Hektor pragnie zamknąć obwód łączący złącza - chciałby aby po przewodach można było "dostać się" z każdego złącza do każdego innego. W tym celu planuje dołożyć przewody na dolnej części płytki - z zachowaniem tych samych zasad jak te dotyczące zastanych już przewodów na górnej części. Czy to możliwe? Pomóż Hektorowi!

Wejście

W pierwszej linii znajduje się jedna liczba całkowita t - liczba zestawów testowych (1 <= t <= 10). Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu pojedynczego zestawu testowego znajduje się jedna parzysta liczba całkowita n (1 <= n <= 1000000) - liczba złącz na linii zasilającej. W kolejnych n/2 liniach znajdują się pary liczb a, b oznaczające że para złącz o tych numerach połączona jest przewodem na górnej części płytki.

Wyjście

Dla każdego zestawu testowego należy w osobnej linii wypisać słowo "NIE", jeśli nie da się zamknąć obwodu na dolnej części płytki zgodnie z zasadami opisanymi w treści. W przeciwnym razie należy wypisać w pierwszej linii słowo "TAK", a następnie n/2 linie zawierające pary liczb całkowitych oddzielonych spacją - numery złącz połączonych łączonych kolejnymi przewodami na dolnej części płytki. Jeśli istnieje wiele rozwiązań, możesz wypisać dowolne z nich. Kolejność liczb w parach i par w liniach jest dowolna.

Przykład

Wejście Wyjście
2
6
1 6
2 3
4 5
12
1 6
2 5
3 4
7 12
9 8
11 10
TAK
1 2
3 4
5 6
TAK
1 12
3 2
5 6
11 4
10 9
7 8
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com