#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int n,m;
vector<int> adj[100];
int d[100];

void bfs(int x) {
	for (int i=1;i<=n;i++) d[i]=-1;
	d[x]=0;
	queue<int> q;
	q.push(x);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		for (int y : adj[x]) {
			if (d[y]==-1) {
				d[y]=d[x]+1;
				q.push(y);
			}
		}
	}
}

int main() {
	freopen("test.in","r",stdin);
	scanf("%d %d",&n,&m);
	for (int i=0;i<m;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	bfs(4);
	for (int i=1;i<=n;i++) {
		printf("%d: %d\n",i,d[i]);
	}
	return 0;
}