Uczta

Limit pamięci: 64 MB

Król Bajtazar organizuje wielką ucztę z okazji swoich 128. urodzin. Postanowił zaproszonych gości usadzić przy okrągłych stołach tak, żeby żaden z gości nie siedział przy stole sam. Wybrał już osób, które mógłby zaprosić na przyjęcie. Następnie uszeregował gości w kolejności od najważniejszych i ponumerował ich kolejno od do (gość numer jest najważniejszy).

Goście są bardzo wymagający: każdy z nich podał królowi wymagania odnośnie do tego, kto może siedzieć po jego prawej stronie. Król chce, aby każdy z zaproszonych gości miał dogodne towarzystwo, toteż nie pozwoli, aby wymagania któregoś z gości nie zostały spełnione. Może się więc okazać, że nie uda się zaprosić wszystkich osób. Bajtazar poprosił Ciebie (nadwornego informatyka) o wyznaczenie najlepszego z możliwych zbiorów zaproszonych gości i przykładowego usadzenia ich przy okrągłych stołach. Król, spytany o to, co miał na myśli, mówiąc o najlepszym zbiorze gości, odpowiedział zaskakująco rzeczowo, jak na -letniego informatycznego laika:

Aby porównać dwa zbiory gości, wybieram osobę o najmniejszym numerze, która należy do dokładnie jednego z porównywanych zbiorów. Ta właśnie osoba należy do lepszego zbioru.

Przy tak określonym porządku można faktycznie jednoznacznie określić, który z potencjalnych zbiorów gości jest najlepszy.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita () oznaczająca liczbę gości. W -tym z kolejnych wierszy znajduje się opis preferencji osoby o numerze . Opis preferencji rozpoczyna się od liczby całkowitej (). Po niej następuje parami różnych numerów osób - są to liczby całkowite z zakresu od do , różne od . Każda taka liczba określa jedną osobę, która może usiąść po prawicy osoby numer . Suma liczb nie przekracza .

W testach wartych punktów zachodzi dodatkowo warunek: jeśli osoba zezwala na posadzenie osoby po swojej prawej stronie, to również osoba zezwala na posadzenie osoby po swojej prawej stronie. W szczególności oznacza to, że te dwie osoby mogą usiąść razem przy jednym, dwuosobowym stole.

W testach wartych punktów da się zaprosić wszystkie osób na przyjęcie.

Wyjście

W pierwszym wierszu wyjścia powinna znaleźć się liczba całkowita , oznaczająca liczbę stołów w znalezionym rozwiązaniu. Następne wierszy powinno zawierać opisy poszczególnych stołów. Opis stołu rozpoczyna się od liczby całkowitej oznaczającej liczbę gości przy nim siedzących. Dalej następuje liczb oznaczających ich numery. Numery gości powinny być podawane kolejno, w porządku przeciwnym do kierunku ruchu wskazówek zegara. Pierwszy z wypisanych gości będzie siedział po prawej stronie ostatniego z gości.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

1
3 1 3 4

W powyższym przykładzie lepiej zaprosić na ucztę osoby , oraz niż osoby , , oraz . Zgodnie z kryterium króla lepszy zbiór wyznacza osoba o numerze .

Autor zadania: Marcin Smulewicz.