Atcoder E - A Gift From the Stars

#include <bits/stdc++.h>
using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ll  long long
#define MOD 1000000007;

#define got cout<<"Yes\n"; return;
#define got0 cout<<"Yes\n"; return 0;

#define bhak cout<<"No\n"; return;
#define bhak0 cout<<"No\n"; return 0;

#define bas cout<<"\n";
#define RADHE_KRISHNA ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

vector<ll> vvvvvvvvvvvvvvvvv;

void solve();

int main() {
    RADHE_KRISHNA

    ll n; cin>>n;
    vector<vector<ll>> vec(n);


    for(ll i=0; i<n-1; ++i){
        ll a, b; cin>>a>>b;
        a--,b--;

        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    map<ll,ll> mp;
    for(ll i=0; i<n; ++i){
        mp[i] = vec[i].size();
    }

    queue<int> qu;
    vector<bool> vis(n, 0);

    for(ll i=0; i<n; ++i){
        if(mp[i]==1){
            qu.push(i);
            vis[i] = 1;
        }
    }

    vector<ll> ans;

    while(!qu.empty()){
        ll sz = qu.size();

        for(ll _=0; _<sz; ++_){
            ll a = qu.front();
            qu.pop();

            ll par = -1;
            cout<<a+1<<" ";
            for(auto b : vec[a]){
                if(!vis[b]){
                    par = b;
                    break;
                }
            }

            cout<<par+1; bas

            if(!vis[par]){
                vis[par] = 1;

                vector<ll> v1 = vec[par];

                for(int j=0; j<v1.size(); ++j){
                    ll v = v1[j];
                    vis[v] =1;

                    vector<ll> v2 = vec[v];

                    for(ll t=0; t<v2.size(); ++t){
                        ll e = v2[t];
                        if(!vis[e]){
                            mp[e]--;
                        }
                    }
                }

            }


        }

        for(ll i=0; i<n; ++i){
            if(mp[i]==1 && !vis[i]){
                qu.push(i);
                vis[i] = 1;
            }
        }
    }

    sort(ans.begin(), ans.end());

    for(auto a : ans){
        cout<<a<<" ";
    }
    bas

    return 0;
}