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