【題解】CSES 1134 Prüfer Code

#include <iostream>
#include <set>
using namespace std;
 
int n, a[200005], cnt[200005];
set <int> st;
 
int main() {
    cin >> n;
    for (int i = 1; i <= n-2; i++){
        cin >> a[i];
        cnt[a[i]]++;
    }
    for (int i = 1; i <= n; i++){
        if (!cnt[i]) st.insert(i);
    }
    for (int i = 1; i <= n-2; i++){
        cout << *st.begin() << " " << a[i] << "\n";
        st.erase(*st.begin());
        cnt[a[i]]--;
        if (!cnt[a[i]]) st.insert(a[i]);
    }
    cout << *st.begin() << " ";
    st.erase(*st.begin());
    cout << *st.begin() << "\n";
}