Sparing w Programowaniu Politechnika Poznańska, 10.03.2007

Opis

Twoim zadaniem jest podzielenie pewnej grupy ludzi na dwie drużyny, w taki sposób, że:

• każdy należy do jednej drużyny;
• każda drużyna ma przynajmniej jednego członka;
• każda osoba w drużynie zna każdego z pozostałych członków drużyny;
• drużyny mają możliwie najmniejszą rożnice rozmiarów

To zadanie może mieć wiele rozwiązań. Masz znaleźć i wypisać dowolne z nich lub informację, że szukane rozwiązanie nie istnieje.

Specyfikacja wejścia

Dla uproszczenia każda osoba ma przypisaną unikalną liczbę całkowitą z zakresu od 1 do N.

Wpierwszej linii znajduję się pojedyncza liczba D (1 ≤ D ≤ 300) określająca liczbę testów

Wpierwszej linii testu znajduje się liczba całkowita N (2 ≤ N ≤ 100) - liczba ludzi, których trzeba przypisać do drużyn, a po niej N linii, po jednej na osobę, według rosnących identyfikatorów. Każda linia zawiera listę parami różnych liczb A_ij (1 ≤ A_ij ≤ N, A_ij ≠ i) oddzielonych spacjami. Lista ta reprezentuje identyfikatory osób, które zna i-ta osoba. Lista zakończona jest liczbą 0.

Specyfikacja wyjścia

Jeżeli rozwiązanie dla problemu nie istnieje, wypisz -1. W przeciwnym wypadku zapisz rozwiązanie w dwóch liniach. W pierwszej napisz liczbę osób w pierwszej drużynie, a po niej identyfikatory osób z tej drużyny odzielone pojedynczą spacją. W drugiej linii opisz w ten sam sposób drugą drużynę. Kolejność drużyn oraz identyfikatorów w każdej drużynie jest dowolna.

Przykład

2
5
3 4 5 0
1 3 5 0
2 1 4 5 0
2 3 5 0
1 2 3 4 0
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0

-1
3 1 3 5
2 2 4