题解：AT_abc251_f Two Spanning Trees

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	} 
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
const int N=5*114514; 
int n,m;
vector<int> g[N];
int fa1[N],fa2[N];	//分别代表 dfs 的父亲和 bfs 的父亲 
void dfs(int u){
//	cout<<'!'<<u<<endl;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
//		cout<<'#'<<v<<endl;
		if(!fa1[v]){
			fa1[v]=u;
			write1(u),write2(v);
			dfs(v);
		}
	}
} 
void bfs(int u){
	queue<int> q;
	q.push(u);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(!fa2[v]){
				fa2[v]=u;
				write1(u),write2(v);
				q.push(v);	//再加入一个新点  
			}
		}
	}
}
signed main(){
	n=read(),m=read();
	while(m--){
		int u=read(),v=read();
		g[u].push_back(v),g[v].push_back(u);
	}
	fa1[1]=fa2[1]=n+1;	//免得之后再来处理  
	dfs(1),bfs(1);
	return 0;
}//在寂寞的时分 无论飞向何方