Distances

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
using namespace std;
const int N=110;
int dist[N][N];
vector<int>g[N];
void dfs(int v,int pr,int root,int cur){
    dist[root][v]=cur;
    for (int to:g[v]){
        if (to!=pr){
            dfs(to,v,root,cur+1);
        }
    }
}
int p[N];
mt19937 rnd(time(NULL));
double random_double(){
    return rnd()%1000000001/1000000000.0;
}
void solve(){
    int n;cin>>n;
    for (int i=0;i<=n;i++) g[i].clear();
    for (int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=1;i<=n;++i){
        dfs(i,0,i,0);
    }
    for (int i=1;i<=n;i++) p[i]=i;
    random_shuffle(p+1,p+n+1);
    int f=0;
    for (int i=1;i<n;i++) f=max(f,dist[p[i]][p[i+1]]);
    int cnt=0;
    for (double temp=2000.0;temp>=0.0001;temp*=0.99998){
        cnt++;
        int l=rnd()%n+1;
        int r=rnd()%n+1;
        if (l>r) swap(l,r);
        reverse(p+l,p+r+1);
        int nw=0;
        for (int i=1;i<n;i++) nw=max(nw,dist[p[i]][p[i+1]]);
        double delta=nw-f;
        if (delta<0.0 || exp(-delta/temp)<random_double()){
            nw=f;
        } else {
            reverse(p+l,p+r+1);
        }
    }
//    cout<<cnt<<endl;
//    if (f>3) exit(1);
    for (int i=1;i<=n;i++) cout<<p[i]<<" ";
    cout<<endl;






}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt;cin>>tt;
    while (tt--){
        solve();
    }
    return 0;
}

//1 2 3 3 2 1
//1 (1) 3 (1) 5 6
//6 7 8
//1 2 3 4 5 6

Test 1

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED