Distances

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = a - 1; i >= (b); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set
#define INF 1000000000

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;

vi graph[101];
int n, tc, ans[101], indx, dist;

void solve(int u, int p) {
    bool add = true;
    if(dist==3){
        add=false;
        ans[indx++]=u;
        dist=0;
    }
    trav(v, graph[u]) {
        if (v == p) continue;
        ++dist;
        solve(v, u);
    }

    if (add) {
        ans[indx++] = u;
        dist = 0;
    }
    ++dist;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> tc;
    int u, v;
    while (tc--) {
        fill(graph, graph + 101, vi());
        cin >> n;
        rep(i, 0, n-1) {
            cin >> u >> v;
            graph[u].pb(v);
            graph[v].pb(u);
        }
        indx = dist = 0;
        solve(1, 0);
        rep(i,0,n)cout<<ans[i]<<' ';
        cout<<endl;
    }
    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED