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.