package Recursion;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

public class GraphMinDistance {

static int n, m = 0;

static ArrayList<ArrayList<Integer>> graph;

static int[] ch, dis;

public static void bfs(int v) {

Queue<Integer> queue = new LinkedList<>();

queue.offer(v);

ch[v] = 1;

dis[v] = 0;

while (!queue.isEmpty()) {

int cur = queue.poll();

for (int nv : graph.get(cur)) {

if (ch[nv] == 0) {

ch[nv] = 1;

queue.offer(nv);

dis[nv] = dis[cur] + 1;

}

}

}

}

public void main() {

Scanner in=new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

graph = new ArrayList<>();

for (int i = 0; i <= n; i++) {

graph.add(new ArrayList<Integer>());

}

ch = new int[n + 1];

dis = new int[n + 1];

for (int i = 0; i < m; i++) {

int a = in.nextInt();

int b = in.nextInt();

graph.get(a).add(b);

}

ch[1] = 1;

bfs(1);

for (int i = 2; i <= n; i++) {

System.out.print(i + ":" + dis[i] + " ");

}

}

}