Distances

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define N 2000005
#define INF 1e9+5
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define fori(i,l,r) for(int i=l;i<=r;i++)
#define forf(i,r) fori(i,1,r)
#define rof(i,r,l) for(int i=r;i>=l;i--)
#define ll long long
#define int ll
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> vec(n);
    iota(vec.begin(),vec.end(),1);
    vector<int> g[n+1];
    int dist[n+1][n+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)
                dist[i][j]=0;
            else
                dist[i][j]=INF;
        }
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin >> x >> y;
        dist[x][y]=1;
        dist[y][x]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(dist[i][j]>dist[i][k]+dist[k][j]){
                    dist[i][j]=dist[i][k]+dist[k][j];
                    dist[j][i]=dist[i][j];
                }
            }
        }
    }
    do{
        bool flag=true;
        for(int i=0;i<n-1;i++){
            if(dist[vec[i]][vec[i+1]]>3){
                flag=false;
            }
        }
        if(flag){
            for(int i:vec)
                cout << i << sp;
            cout << nl;
            return;
        }
    }while(next_permutation(vec.begin(),vec.end()));
    cout << -1 << nl;
}

int32_t main(){
	fastio()
	int t=1;
	cin >> t;
	while(t--){
		solve();
	}
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED