rt，用的n log n做法，然而所有基环树的情况都WA
甚至样例2都不过

#include<bits/stdc++.h>
#define debug() cout<<"QWQ"<<endl;
#define endl "\n"
using namespace std;

const int N=500010;
int n,m;
struct node{
	int v,nxt;
}eg[N<<1];
int cnt,hd[N];
bool mk[N];

inline void add(int a,int b)
{
	cnt++;
	eg[cnt]={b,hd[a]};
	hd[a]=cnt;
}

void dfs(int nw)
{
	cout<<nw<<" ";
	mk[nw]=true;
	priority_queue<int,vector<int>, greater<int> > q;
	for(int i=hd[nw];i;i=eg[i].nxt)
	{
		int to=eg[i].v;
		if(mk[to]) continue;
		q.push(to);
	}
	while(!q.empty())
	{
		dfs(q.top());
		q.pop();
	}
}

bool ins[N],flag,t;
int s;//环的起始点
void findsic(int nw,int fa)
{
	mk[nw]=true;
	for(int i=hd[nw];i;i=eg[i].nxt)
	{
		int to=eg[i].v;
        if(to==fa) continue;
		if(!mk[to])
		{
			findsic(to,nw);
            if(flag)
            {
                ins[nw]=t;
    			if(nw==s) t=false;
                return;
            }
		}else{
			s=to;
			flag=true;
			t=true;
			ins[nw]=true;
            return;
		}
	}
}

int val[N];
void dfssic(int nw)
{
	mk[nw]=true;
	cout<<nw<<" ";
	priority_queue<int, vector<int>, greater<int> > q;
	for(int i=hd[nw];i;i=eg[i].nxt)
	{
		int to=eg[i].v;
		if(mk[to]) continue;
		q.push(to);
	}
	if(!ins[nw] || (!flag && nw != s))
	{
		while(!q.empty())
		{
			dfssic(q.top());
			q.pop();
		}
    }else if(nw==s){
		while(!q.empty())
		{
			int to=q.top();
			q.pop();
			if(!ins[to]) dfssic(to);
			if(flag)
			{
				flag=false;
				if(!mk[nw]) dfssic(nw);
			}else{
				val[to]=q.top();
				flag=true;
				dfssic(to);
				continue;
			}
		}
	}else if(flag)
    {
		while(!q.empty())
		{
			int to=q.top();
			q.pop();
			if(!mk[to]) dfssic(to);
			else{
				if(!q.empty()) val[to]=q.top();
				else val[to]=val[nw];
				if(val[to] < to) dfssic(val[to]);//老师讲的：如果通过环点更优，就走，否则就切断这条边
				else dfssic(to);
			}
		}
	}
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	if(m<n)
	{
		dfs(1);
		return 0;
	}
	findsic(1,-1);
	memset(mk,false,sizeof mk);
	flag=false;
	dfssic(1);
	return 0;
}