autor zadania: Wojciech Sirko
Bajtolandia, państwo podziemne, jest w zagrożeniu. Z powodu braku remontów zaczynają się zawalać tunele łączące poszczególne miasta. Bajtolandia składa się z miast połączonych tunelami dwukierunkowymi, które nie przecinają się ze sobą (jeden może być poprowadzony nad drugim). Każdą parę miast łączy co najwyżej jeden tunel. Bajtazar, król Bajtolandii, otrzymał od swoich doradców listę z opisem Bajtolandii. Na liście znajduje się, dokładnie raz, opis każdego tunelu. Dodatkowo Bajtazar dowiedział się od doradców, że, zaczynając od jutra, każdego dnia będzie się zawalać dokładnie jeden tunel, w kolejności, w jakiej są na liście. Bajtazar wyznaczył Ciebie, swojego zaufanego doradcę, abyś policzył, którego dnia najwcześniej sytuacja stanie się krytyczna (dzisiaj jest dzień pierwszy), czyli państwo zostanie podzielone na dokładnie k zespołów miast. Jeśli jakieś miasto należy do zespołu, to należą też do niego wszystkie miasta, z którymi połączone jest ono niezawalonymi tunelami.
W pierwszej linii wejścia znajdują się trzy liczby całkowite n, m i k (1 <= n, k <= 100000; 0 <= m <= 200000). Oznacza to, że Bajtolandia składa się z n miast i m tuneli. Następnie mamy opis Bajtolandii składający się z m linii. Każda linia opisuje jeden tunel i składa się z dwóch liczb całkowitych (1 <= ai < bi <= n). Oznacza to, że miasta o numerze ai i bi łączy dwukierunkowy tunel. Tunele będą się zawalać w kolejności, w jakiej są na liście (każdy tunel występuje dokładnie raz).
Jedna liczba oznaczająca najmniejszy numer dnia, którego Bajtolandia będzie podzielona na dokładnie k zespołów.
wejście:
5 5 3 1 2 2 3 3 4 1 4 3 5
wyjście:
4[Zgłoś rozwiązanie] [Moje zgłoszenia]
2023-10-02 9:32:42Kółko informatyczne
Marek Sommer, Joanna Śmigielska,
Maciej Matraszek, Michał Adamczyk, Maciej Dębski