#include <iostream>
using namespace std;
#include<vector>
#include <bits/stdc++.h>
int main() {
	// your code goes here
	int n,m;
	cin>>n>>m;
	vector<int>g[n+5];
	
	int x,y;
	for(int i=1;i<=m;i++)
	 {
	 	cin>>x>>y;
	 	g[x].push_back(y);
	 	g[y].push_back(x);
	 }
	 int source=1;
	 int used[n+5]={0};
	 int level[n+5]={0};
	 queue<int>q;
	 q.push(source);
	 used[source]=1;
	 level[source]=0;
	 while(!q.empty())
	  {
	  	int removed;
	  	removed = q.front();
	    cout<<removed<<"-"<<level[removed]<<endl;
	  	q.pop();
	  	
	  	for(auto x:g[removed])
	  	 {
	  	 	if(used[x]==0)
	  	 	 {
	  	 	 	q.push(x);
	  	 	 }	
	  	 	used[x]=1;
	  	 	level[x]=level[removed]+1;
	  	 	
	  	 }
	  	
	  }
	  i=1;
	 //while(i<=n)  For each input graph print the shortest distance of each node from the source node.
	 //{              serial wise...
	 //	cout<<level[i]<<" ";
	 //}
	 
	return 0;
}