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.