#include<bits/stdc++.h>
#define N 100000
#define ll long long
#define rr register
using namespace std;
inline int read(){
	int num=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') num=num*10+ch-'0',ch=getchar();
	return f?-num:num; 
}
const int mod=1000000007;
int head[N],cnt=1,nxt[N];
inline void add(int x,int y){
	nxt[++cnt]=head[x],head[x]=cnt,qu[cnt]=y;
}
int dep[N],fa[N][19],dist[N];
inline void bfs(){
	queue<int> q;
	dep[1]=1;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=qu[i];
			if(dep[y]) continue;
			dep[y]=dep[x]+1;
			dist[y]=dist[x]+1;
			fa[y][0]=x;
			for(int j=1;j<=18;j++) fa[y][j]=fa[fa[y][j-1]][j-1];
			q.push(y);
		}
	}
}
inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=18;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=18;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
inline void lca()
int main(){
	int n=read(),m=read();
	for(rr int i=0,x,y;i<m;i++)
		x=read(),y=read(),add(x,y),add(y,x);
	for(int i=1;i<=n;i++){
		for(int i=1;i<=n;i++){
			
		}
	}
	return 0;
}