Jaskinia
Limit pamięci: 256 MB
Bajtazar odkrył jaskinię.
Okazało się, że jaskinia ta składa się z
komnat połączonych korytarzami w taki sposób,
że między dowolnymi dwiema komnatami można przejść na dokładnie jeden sposób.
Jaskinię trzeba teraz staranniej zbadać, dlatego Bajtazar poprosił swoich kolegów o pomoc.
Wszyscy przybyli na miejsce i chcą podzielić się na grupy.
Każdej grupie przypadnie do zbadania tyle samo komnat, a każda komnata zostanie przydzielona dokładnie jednej grupie.
Dodatkowo, żeby ekipy nie wchodziły sobie w drogę, każda z nich powinna być w stanie poruszać się pomiędzy przydzielonymi sobie komnatami bez przechodzenia przez komnaty przydzielone innym grupom.
Na ile grup mogą podzielić się badacze jaskini?
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(
), oznaczającą liczbę komnat w jaskini.
Komnaty są ponumerowane od
do
.
Kolejne
wierszy opisuje połączenia między komnatami.
W
-tym spośród nich znajduje się liczba
(
), która reprezentuje korytarz łączący komnaty o numerach
oraz
.
Wyjście
Wypisz jeden wiersz zawierający wszystkie takie liczby
, że komnaty w jaskini można podzielić na
rozłącznych zbiorów
równej wielkości, a pomiędzy dowolnymi dwiema komnatami w każdym zbiorze można przejść, korzystając jedynie z komnat z tego zbioru.
Liczby należy wypisać w kolejności rosnącej, pooddzielane pojedynczymi odstępami.
Przykład
Dla danych wejściowych:
6
1
2
3
3
5
poprawną odpowiedzią jest:
1 3 6
Autor zadania: Jakub Łącki.