Biura

Limit pamięci: 64 MB

Firma Bajtel jest potentatem na bajtockim rynku telefonów komórkowych. Każdy jej pracownik otrzymał służbowy telefon, w którym ma zapisane numery telefonów niektórych swoich współpracowników (a wszyscy ci współpracownicy mają w swoich telefonach zapisany jego numer). W związku z dynamicznym rozwojem firmy zarząd postanowił przenieść siedzibę firmy do nowych biurowców. W celu polepszenia efektywności pracy zostało postanowione, że każda para pracowników, którzy będą pracować w różnych budynkach, powinna znać (nawzajem) swoje numery telefonów, tzn. powinni oni mieć już zapisane nawzajem swoje numery w służbowych telefonach komórkowych. Równocześnie, zarząd postanowił zająć jak największą liczbę biurowców, aby zapewnić pracownikom komfort pracy. Pomóż zarządowi firmy Bajtel zaplanować liczbę biur i ich wielkości tak, aby spełnić oba te wymagania.

Zadanie

Napisz program, który:

• wyczyta ze standardowego wejścia opis, czyje numery telefonów mają zapisane w swoich telefonach komórkowych poszczególni pracownicy,
• wyznaczy maksymalną liczbę biurowców oraz ich wielkości, spełniające warunki postawione przez zarząd firmy Bajtel,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite: oraz (, ), oddzielone pojedynczym odstępem i oznaczające odpowiednio: liczbę pracowników firmy Bajtel i liczbę par współpracowników, którzy mają zapisane nawzajem swoje numery telefonów w swoich telefonach komórkowych. Pracownicy firmy są ponumerowani od do .

Każdy z kolejnych wierszy zawiera po jednej parze liczb całkowitych i ( dla ), oddzielonych pojedynczym odstępem i oznaczających, że pracownicy o numerach i mają zapisane nawzajem swoje numery telefonów w swoich telefonach komórkowych. Każda para liczb oznaczających pracowników pojawi się na wejściu co najwyżej raz.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą: maksymalną liczbę biurowców, które powinna zająć firma Bajtel. Drugi wiersz wyjścia powinien zawierać niemalejący ciąg dodatnich liczb całkowitych, pooddzielanych pojedynczymi odstępami, oznaczających wielkości biurowców (liczby rozlokowanych w nich pracowników). Jeżeli istnieje więcej niż jedno poprawne rozwiązanie, Twój program powinien wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7

poprawną odpowiedzią jest:

3
1 2 4

Przykładowy dobry przydział pracowników do biur wygląda następująco: do pierwszego biura pracownik o numerze 4, do drugiego pracownicy 5 i 7, a do trzeciego pracownicy 1, 2, 3 i 6.

Autorzy zadania: Marek Cygan i Jakub Radoszewski.