26635번 - Poddrzewo 스페셜 저지다국어

Gdy uciekasz przed niedźwiedziem, który chce się z Tobą pobawić i/lub skonsumować Cię na kolację, bardzo ważne jest rozpoznać jego gatunek:

• jeśli biegniesz i biegniesz, znajdujesz drzewo i wdrapujesz się na nie, a niedźwiedź za Tobą, to jest to niedźwiedź brunatny,
• jeśli biegniesz i biegniesz, znajdujesz drzewo i wdrapujesz się na nie, a niedźwiedź strząsa Cię z niego, to jest to niedźwiedź grizzly,
• jeśli biegniesz i biegniesz i nie możesz znaleźć drzewa, to jest to niedźwiedź polarny.

Skupmy się zatem na znalezieniu drzewa. W informatyce drzewo to po prostu zbiór k wierzchołków oraz k − 1 krawędzi, z których każda łączy pewne dwa wierzchołki. Połączenia muszą gwarantować, że z każdego wierzchołka da się osiągnąć każdy inny, idąc wyłącznie po krawędziach. Liczbę krawędzi, które wychodzą z wierzchołka nazywamy stopniem tego wierzchołka.

Dany jest ciąg n liczb a₁, a₂, . . . , a_n. Podejrzewasz, że jest to lista stopni wszystkich wierzchołków pewnego drzewa. Niestety, do ciągu zaplątały się pewne przypadkowe liczby, a w dodatku niektóre inne zostały po drodze błędnie przepisane. Usuń niepotrzebne liczby z ciągu i zmień niektóre inne tak, aby faktycznie była to prawidłowa lista stopni.

Formalnie, możesz zmienić kolejność elementów danego ciągu n liczb, usunąć niektóre z nich, po czym zmienić niektóre z pozostałych elementów. Dla uzyskanego ciągu liczb d₁, d₂, . . . , d_k musisz podać drzewo o k ≥ 2 wierzchołkach (ponumerowanych od 1 do k) takie, że d_i to stopień i-tego wierzchołka. Zarówno liczba usuniętych, jak i zmienionych wierzchołków może być dowolna (także równa 0) – Twoim zadaniem jest znaleźć rozwiązanie o minimalnej liczbie zmienionych wierzchołków.

Pierwszy wiersz wejścia zawiera liczbę całkowitą n (2 ≤ n ≤ 10⁶) – liczbę elementów ciągu. Kolejny wiersz zawiera ciąg n liczb całkowitych a₁, a₂, . . . , a_n (1 ≤ a_i ≤ n − 1).

W pierwszym wierszu wypisz liczbę zmienionych elementów x (tę wartość masz zminimalizować). W drugim wierszu wypisz rozmiar drzewa k (2 ≤ k ≤ n). W każdym z kolejnych k − 1 wierszy wypisz po dwie liczby u_i oraz v_i (1 ≤ u_i, v_i ≤ k), opisujące krawędź między wierzchołkami u_i i v_i. Wypisane krawędzie muszą tworzyć drzewo.

Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich. Nie musisz minimalizować ani maksymalizować wartości k.