#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, m;
	cin>>n>>m;
	vector<int> adjList[n];
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		adjList[x].push_back(y);
		adjList[y].push_back(x);
	}
 
	int source=1;
	vector<int> visited(n, 0);
	vector<int> level(n, 0);
	queue<int> q;
	q.push(source);
	visited[source]=1;
	while(!q.empty()){
		int node=q.front();
		cout<<node<<" "<<level[node]<<"\n";
		q.pop();
		visited[node]=1;
		for(auto adjNode : adjList[node]){
			if(!visited[adjNode]){
				q.push(adjNode);
				visited[adjNode]=1;
				level[adjNode]=level[node]+1;
			}
		}
	}
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCWludCBuLCBtOwoJY2luPj5uPj5tOwoJdmVjdG9yPGludD4gYWRqTGlzdFtuXTsKCWZvcihpbnQgaT0wO2k8bTtpKyspewoJCWludCB4LHk7CgkJY2luPj54Pj55OwoJCWFkakxpc3RbeF0ucHVzaF9iYWNrKHkpOwoJCWFkakxpc3RbeV0ucHVzaF9iYWNrKHgpOwoJfQoJCglpbnQgc291cmNlPTE7Cgl2ZWN0b3I8aW50PiB2aXNpdGVkKG4sIDApOwoJdmVjdG9yPGludD4gbGV2ZWwobiwgMCk7CglxdWV1ZTxpbnQ+IHE7CglxLnB1c2goc291cmNlKTsKCXZpc2l0ZWRbc291cmNlXT0xOwoJd2hpbGUoIXEuZW1wdHkoKSl7CgkJaW50IG5vZGU9cS5mcm9udCgpOwoJCWNvdXQ8PG5vZGU8PCIgIjw8bGV2ZWxbbm9kZV08PCJcbiI7CgkJcS5wb3AoKTsKCQl2aXNpdGVkW25vZGVdPTE7CgkJZm9yKGF1dG8gYWRqTm9kZSA6IGFkakxpc3Rbbm9kZV0pewoJCQlpZighdmlzaXRlZFthZGpOb2RlXSl7CgkJCQlxLnB1c2goYWRqTm9kZSk7CgkJCQl2aXNpdGVkW2Fkak5vZGVdPTE7CgkJCQlsZXZlbFthZGpOb2RlXT1sZXZlbFtub2RlXSsxOwoJCQl9CgkJfQoJfQoJcmV0dXJuIDA7Cn0=

NiA4CjAgMQoxIDIKMiAzCjMgNAo0IDUKMCAzCjEgNAoyIDU=

6 8
0 1
1 2
2 3
3 4
4 5
0 3
1 4
2 5