Distances

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize ("trapv")
//#pragma GCC optimize ("sse, ssse, sse2, avx")
 
#define f first
#define s second
#define pb push_back
#define ld long double
#define int long long
 
using namespace std;
 
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 1e18 + 10;
 
vector<int> a[N], ans;
 
void dfs(int u, int pr, int c){
    if(c == 0)
        ans.pb(u + 1);
    for(auto v : a[u])
        if(v != pr)
            dfs(v, u, 1 - c);
    if(c == 1)
        ans.pb(u + 1);
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        for(int i = 0; i < n; ++i)
            a[i].clear();
        ans.clear();
        for(int i = 0; i < n - 1; ++i){
            int u, v; cin >> u >> v;
            a[u - 1].pb(v - 1);
            a[v - 1].pb(u - 1);
        }
        dfs(0, -1, 0);
        for(auto v : ans)
            cout << v << " ";
        cout << "\n";
    }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED