#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M = 0;
vector<int> map[21];
int visit[21];
int dis[21];
queue<int> q;
 
void BFS()
{
	while(!q.empty())
	{
		int current  = q.front(); q.pop();
		for(int i = 0; i < map[current].size(); i++)
		{
			int next = map[current][i];
			if(visit[next] == 0)
			{
				visit[next] = 1;
				dis[next] = dis[current]+1;
				q.push(next);
			}
		}
	}
}
 
int main() {
	// your code goes here
	int a,b = 0;
	cin >> N >> M;
	for(int i = 0 ;  i < M; i++)
	{
		cin >> a >> b;
		map[a].push_back(b);
	}
	visit[1] = 1;
	q.push(1);
	BFS();
	for(int i = 2; i<=N; i++){
		cout << i <<" : " << dis[i] << endl;;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBOLCBNID0gMDsKdmVjdG9yPGludD4gbWFwWzIxXTsKaW50IHZpc2l0WzIxXTsKaW50IGRpc1syMV07CnF1ZXVlPGludD4gcTsKCnZvaWQgQkZTKCkKewoJd2hpbGUoIXEuZW1wdHkoKSkKCXsKCQlpbnQgY3VycmVudCAgPSBxLmZyb250KCk7IHEucG9wKCk7CgkJZm9yKGludCBpID0gMDsgaSA8IG1hcFtjdXJyZW50XS5zaXplKCk7IGkrKykKCQl7CgkJCWludCBuZXh0ID0gbWFwW2N1cnJlbnRdW2ldOwoJCQlpZih2aXNpdFtuZXh0XSA9PSAwKQoJCQl7CgkJCQl2aXNpdFtuZXh0XSA9IDE7CgkJCQlkaXNbbmV4dF0gPSBkaXNbY3VycmVudF0rMTsKCQkJCXEucHVzaChuZXh0KTsKCQkJfQoJCX0KCX0KfQoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglpbnQgYSxiID0gMDsKCWNpbiA+PiBOID4+IE07Cglmb3IoaW50IGkgPSAwIDsgIGkgPCBNOyBpKyspCgl7CgkJY2luID4+IGEgPj4gYjsKCQltYXBbYV0ucHVzaF9iYWNrKGIpOwoJfQoJdmlzaXRbMV0gPSAxOwoJcS5wdXNoKDEpOwoJQkZTKCk7Cglmb3IoaW50IGkgPSAyOyBpPD1OOyBpKyspewoJCWNvdXQgPDwgaSA8PCIgOiAiIDw8IGRpc1tpXSA8PCBlbmRsOzsKCX0KCXJldHVybiAwOwp9

NiA5CjEgMwoxIDQKMiAxCjIgNQozIDQKNCA1CjQgNgo2IDIKNiA1

6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5