W korporacji pracuje $n$ pracowników, z których jeden jest dyrektorem. Każdy pracownik poza dyrektorem ma dokładnie jednego bezpośredniego przełożonego.
Każdy pracownik wykonuje ściśle określoną pracę. Jeżeli pracownik $a$ potrzebuje wykonania pracy, którą zajmuje się pracownik $b$, musi wysłać pracownikowi $b$ zlecenie. Zgodnie z polityką korporacji zlecenia można przekazywać bezpośrednio tylko od pracownika do jego bezpośredniego przełożonego albo odwrotnie — od przełożonego do bezpośredniego podwładnego. Zlecenie jest przekazywane od pracownika do pracownika, aż dotrze do pracownika $b$.
Aby odciążyć pracowników, korporacja zatrudniła $k$ kurierów. Kurier numer $i$ jest przypisany do pary pracowników $a_i$ i $b_i$ i dostarcza zlecenia między nimi. Jeżeli jeden pracownik z tej pary musi przekazać zlecenie drugiemu, oddaje je kurierowi, który kolejno przekazuje zlecenie między pracownikami zgodnie z polityką korporacji, aż przejdzie ono przez wszystkich niezbędnych pracowników pośrednich i zostanie dostarczone adresatowi. Podczas dostarczania jednego zlecenia kurier nie odwiedza żadnego pracownika więcej niż raz.
Aby zoptymalizować koszty, postanowiono znaleźć parę kurierów, których trasy pokrywają się w największym stopniu, i zrezygnować z usług jednego z nich, powierzając jego pracę drugiemu. Stopniem dublowania pracy pary kurierów nazwiemy liczbę przejść między pracownikiem a jego bezpośrednim przełożonym, w dowolnym kierunku, należących do trasy zarówno pierwszego, jak i drugiego kuriera.
Należy napisać program, który wyznaczy dwóch kurierów o największym stopniu dublowania pracy.
Wejście
Pierwszy wiersz zawiera dwie liczby całkowite: $n$ — liczbę pracowników, oraz $k$ — liczbę kurierów ($2 \le n,k \le 2\cdot10^5$). Pracownicy są ponumerowani od $1$ do $n$, a dyrektor ma numer $1$.
Drugi wiersz zawiera $n-1$ liczb całkowitych: $p_2,p_3,\ldots,p_n$ — numery bezpośrednich przełożonych każdego pracownika poza dyrektorem ($1 \le p_i < i$).
Następne $k$ wierszy zawiera po dwie liczby całkowite: $a_i$ i $b_i$ — numery pracowników w parze, do której przypisany jest kurier numer $i$ ($1 \le a_i,b_i \le n$; $a_i\ne b_i$). Do tej samej pary pracowników może być przypisanych kilku kurierów.
Wyjście
Pierwszy wiersz powinien zawierać jedną liczbę całkowitą — największy stopień dublowania pracy dwóch kurierów.
Drugi wiersz powinien zawierać dwie różne liczby całkowite od $1$ do $k$ — numery kurierów tworzących parę o największym stopniu dublowania pracy. Jeśli takich par jest kilka, można wypisać dowolną z nich.
Uwagi
Powiemy, że pracownik $a$ podlega poleceniom pracownika $b$, jeżeli $b$ jest bezpośrednim przełożonym $a$ albo bezpośredni przełożony $a$ podlega poleceniom pracownika $b$. Naturalne jest nazywanie ważnym kuriera, który przekazuje zlecenia od pracownika do kogoś, kto podlega jego poleceniom (lub w przeciwnym kierunku).
Podzadania
| Numer podzadania | Punkty | $n$ | $k$ | Dodatkowe ograniczenia | Wymagane podzadania |
|---|---|---|---|---|---|
| 1 | 29 | $2 \le n \le 100$ | $2 \le k \le 100$ | — | |
| 2 | 12 | $2 \le n \le 4000$ | $2 \le k \le 1000$ | — | 1 |
| 3 | 7 | $2 \le n \le 10^5$ | $2 \le k \le 1000$ | — | 1–2 |
| 4 | 8 | $2 \le n \le 10^5$ | $2 \le k \le 5000$ | — | 1–3 |
| 5 | 10 | $2 \le n \le 10^5$ | $2 \le k \le 50\,000$ | Liczba przejść między dowolnym pracownikiem a dyrektorem nie przekracza $20$ | |
| 6 | 12 | $2 \le n \le 10^5$ | $2 \le k \le 50\,000$ | Każdy kurier jest ważny | |
| 7 | 12 | $2 \le n \le 10^5$ | $2 \le k \le 50\,000$ | — | 1–6 |
| 8 | 10 | $2 \le n \le 2\cdot10^5$ | $2 \le k \le 2\cdot10^5$ | — | 1–7 |
Przykład
Wejście 1
4 2 1 2 2 1 3 1 4
Wyjście 1
1 2 1
Wejście 2
4 2 1 2 3 1 2 3 4
Wyjście 2
0 1 2
Wejście 3
7 3 1 2 2 4 5 5 1 3 3 7 6 1
Wyjście 3
2 2 3
Wejście 4
4 3 1 2 3 1 4 4 1 1 4
Wyjście 4
3 2 1
Uwagi
W pierwszym przykładzie jest dwóch kurierów. Pierwszy dostarcza zlecenia od pracownika $1$ do pracownika $3$ lub odwrotnie. Na przykład, dostarczając zlecenie od pracownika $1$ do pracownika $3$, najpierw przekazuje je od pracownika $1$ pracownikowi $2$, a następnie od pracownika $2$ pracownikowi $3$. Drugi kurier dostarcza zlecenia od pracownika $1$ do pracownika $4$ lub odwrotnie. Na przykład, dostarczając zlecenie od pracownika $4$ do pracownika $1$, najpierw przekazuje je od pracownika $4$ pracownikowi $2$, a następnie od pracownika $2$ pracownikowi $1$. Stopień dublowania pracy tej pary kurierów wynosi $1$, ponieważ wspólne jest dla nich przejście między pracownikiem $1$ (dyrektorem) a pracownikiem $2$.
W drugim przykładzie również jest dwóch kurierów, lecz ich trasy się nie przecinają.
Trzeci przykład przedstawiono na powyższym rysunku. Grube linie oznaczają przejścia między pracownikami. Cienkie linie oznaczają trasę pierwszego kuriera między pracownikami $1$ i $3$. Długie kreski oznaczają trasę drugiego kuriera między pracownikami $3$ i $7$. Krótkie kreski oznaczają trasę trzeciego kuriera między pracownikami $1$ i $6$.
Do tras pierwszego i drugiego kuriera należy wspólnie tylko przejście między pracownikami $2$ i $3$. Do tras pierwszego i trzeciego kuriera należy wspólnie tylko przejście między pracownikami $1$ i $2$. Do tras drugiego i trzeciego kuriera należą wspólnie dwa przejścia: między pracownikami $2$ i $4$ oraz między pracownikami $4$ i $5$. Zatem para kurierów o numerach $2$ i $3$ ma największy stopień dublowania pracy, równy $2$.
W czwartym przykładzie wszyscy kurierzy przenoszą zlecenia między dyrektorem a pracownikiem numer $4$. Zatem wszystkie pary kurierów mają stopień dublowania pracy równy $3$. Można wypisać dowolną parę.
Informacje ogólne o zadaniach drugiej rundy
Dostęp do wyników sprawdzania rozwiązań podczas rundy
We wszystkich zadaniach można dowolnie wiele razy pytać o wynik ostatecznego sprawdzenia. Dla każdego podzadania podawane są zdobyte punkty oraz wynik sprawdzenia programu na każdym teście.
Ograniczenie rozmiaru kodu źródłowego
We wszystkich zadaniach rozmiar pliku z kodem źródłowym rozwiązania nie może przekraczać 256 KB.
Proces testowania
We wszystkich zadaniach punkty za podzadanie są przyznawane tylko po zaliczeniu wszystkich jego testów. W tabeli punktacji dla każdego podzadania podano numery wymaganych podzadań. Testy danego podzadania są uruchamiane tylko wtedy, gdy wszystkie wymagane podzadania zostały zaliczone.
Uwagi
W zadaniach z dużą ilością danych wejściowych jury zaleca uczestnikom używającym języków z grupy C/C++ wysyłanie rozwiązań do sprawdzenia z kompilatorem LINUX GNU C++ oraz wczytywanie danych za pomocą scanf.
Należy zwrócić uwagę, że podczas tej rundy można wysyłać rozwiązania w językach Java i Python, a także rozwiązania zadania interaktywnego pod systemem Ubuntu Linux.
Informacje ogólne o zadaniach drugiej rundy
Dostęp do wyników sprawdzania rozwiązań podczas rundy
We wszystkich zadaniach można dowolnie wiele razy pytać o wynik ostatecznego sprawdzenia. Dla każdego podzadania podawane są zdobyte punkty oraz wynik sprawdzenia programu na każdym teście.
Ograniczenie rozmiaru kodu źródłowego
We wszystkich zadaniach rozmiar pliku z kodem źródłowym rozwiązania nie może przekraczać 256 KB.
Proces testowania
We wszystkich zadaniach punkty za podzadanie są przyznawane tylko po zaliczeniu wszystkich jego testów. W tabeli punktacji dla każdego podzadania podano numery wymaganych podzadań. Testy danego podzadania są uruchamiane tylko wtedy, gdy wszystkie wymagane podzadania zostały zaliczone.
Uwagi
W zadaniach z dużą ilością danych wejściowych jury zaleca uczestnikom używającym języków z grupy C/C++ wysyłanie rozwiązań do sprawdzenia z kompilatorem LINUX GNU C++ oraz wczytywanie danych za pomocą scanf.
Należy zwrócić uwagę, że podczas tej rundy można wysyłać rozwiązania w językach Java i Python, a także rozwiązania zadania interaktywnego pod systemem Ubuntu Linux.
Informacje ogólne o zadaniach drugiej rundy
Dostęp do wyników sprawdzania rozwiązań podczas rundy
We wszystkich zadaniach można dowolnie wiele razy pytać o wynik ostatecznego sprawdzenia. Dla każdego podzadania podawane są zdobyte punkty oraz wynik sprawdzenia programu na każdym teście.
Ograniczenie rozmiaru kodu źródłowego
We wszystkich zadaniach rozmiar pliku z kodem źródłowym rozwiązania nie może przekraczać 256 KB.
Proces testowania
We wszystkich zadaniach punkty za podzadanie są przyznawane tylko po zaliczeniu wszystkich jego testów. W tabeli punktacji dla każdego podzadania podano numery wymaganych podzadań. Testy danego podzadania są uruchamiane tylko wtedy, gdy wszystkie wymagane podzadania zostały zaliczone.
Uwagi
W zadaniach z dużą ilością danych wejściowych jury zaleca uczestnikom używającym języków z grupy C/C++ wysyłanie rozwiązań do sprawdzenia z kompilatorem LINUX GNU C++ oraz wczytywanie danych za pomocą scanf.
Należy zwrócić uwagę, że podczas tej rundy można wysyłać rozwiązania w językach Java i Python, a także rozwiązania zadania interaktywnego pod systemem Ubuntu Linux.