暴力拆掉每一条边试一下
因为拆的如果是树上的边就会不连通所以判掉就没问题（笑）
因为n<=5000所以随便暴力也没有问题（笑）
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int u[10010],v[10010],ban,dfs_clock,cnt,n,m,ans[10010],mid[10010],idx[10010],nxt[10010],fir[10010],vis[10010];
vector<pair<int,int> > to[10010];
void addedge(int ui,int vi,int id){
++cnt;
u[cnt]=ui;
v[cnt]=vi;
idx[cnt]=id;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
void dfs(int u,int f){
++dfs_clock;
mid[dfs_clock]=u;
if(vis[u])
return;
vis[u]=true;
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==f)
continue;
if(idx[i]==ban)
continue;
dfs(v[i],u);
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
to[a].push_back(make_pair(b,i));
to[b].push_back(make_pair(a,i));
}
for(int i=1;i<=n;i++)
sort(to[i].begin(),to[i].end());
for(int i=1;i<=n;i++){
for(int j=to[i].size()-1;j>=0;j--){
addedge(i,to[i][j].first,to[i][j].second);
}
}
memset(ans,0x3f,sizeof(ans));
if(m==n)
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)
vis[j]=false;
ban=i;
dfs_clock=0;
dfs(1,0);
if(dfs_clock<n)
continue;
bool f=false;
for(int j=1;j<=n;j++){
if(ans[j]==mid[j])
continue;
if(ans[j]<mid[j])
break;
if(ans[j]>mid[j]){
f=true;
break;
}
}
if(f)
for(int j=1;j<=n;j++)
ans[j]=mid[j];
}
else{
ban=-1;
dfs_clock=0;
dfs(1,0);
bool f=false;
for(int i=1;i<=n;i++){
if(ans[i]==mid[i])
continue;
if(ans[i]<mid[i])
break;
if(ans[i]>mid[i]){
f=true;
break;
}
}
if(f)
for(int i=1;i<=n;i++)
ans[i]=mid[i];
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}