/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();
 
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <=n; i++) {
            graph.add(new ArrayList<>());
        }
 
        for (int i = 1; i <= e; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
 
        // BFS
        Queue<Integer> q=new LinkedList<>();
        int [] visited = new int [n+1];
        int []level=new int [n+5];
        level[1]=0;
        q.add(1);
        visited[1]=1;
        while(!q.isEmpty()){
            int removed=q.poll();
            System.out.println("Node "+removed + " has level "+level[removed]);
 
            for(int u : graph.get(removed)){
                if(visited[u]==0){
                    q.add(u);
                    visited[u]=1;
                    level[u]=level[removed]+1;
                }
            }
        }
        sc.close();
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKICAgICAgICBTY2FubmVyIHNjID0gbmV3IFNjYW5uZXIoU3lzdGVtLmluKTsKICAgICAgICBpbnQgbiA9IHNjLm5leHRJbnQoKTsKICAgICAgICBpbnQgZSA9IHNjLm5leHRJbnQoKTsKIAogICAgICAgIEFycmF5TGlzdDxBcnJheUxpc3Q8SW50ZWdlcj4+IGdyYXBoID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPD1uOyBpKyspIHsKICAgICAgICAgICAgZ3JhcGguYWRkKG5ldyBBcnJheUxpc3Q8PigpKTsKICAgICAgICB9CiAKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBlOyBpKyspIHsKICAgICAgICAgICAgaW50IHUgPSBzYy5uZXh0SW50KCk7CiAgICAgICAgICAgIGludCB2ID0gc2MubmV4dEludCgpOwogICAgICAgICAgICBncmFwaC5nZXQodSkuYWRkKHYpOwogICAgICAgICAgICBncmFwaC5nZXQodikuYWRkKHUpOwogICAgICAgIH0KIAogICAgICAgIC8vIEJGUwogICAgICAgIFF1ZXVlPEludGVnZXI+IHE9bmV3IExpbmtlZExpc3Q8PigpOwogICAgICAgIGludCBbXSB2aXNpdGVkID0gbmV3IGludCBbbisxXTsKICAgICAgICBpbnQgW11sZXZlbD1uZXcgaW50IFtuKzVdOwogICAgICAgIGxldmVsWzFdPTA7CiAgICAgICAgcS5hZGQoMSk7CiAgICAgICAgdmlzaXRlZFsxXT0xOwogICAgICAgIHdoaWxlKCFxLmlzRW1wdHkoKSl7CiAgICAgICAgICAgIGludCByZW1vdmVkPXEucG9sbCgpOwogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk5vZGUgIityZW1vdmVkICsgIiBoYXMgbGV2ZWwgIitsZXZlbFtyZW1vdmVkXSk7CiAgICAgICAgICAgIAogICAgICAgICAgICBmb3IoaW50IHUgOiBncmFwaC5nZXQocmVtb3ZlZCkpewogICAgICAgICAgICAgICAgaWYodmlzaXRlZFt1XT09MCl7CiAgICAgICAgICAgICAgICAgICAgcS5hZGQodSk7CiAgICAgICAgICAgICAgICAgICAgdmlzaXRlZFt1XT0xOwogICAgICAgICAgICAgICAgICAgIGxldmVsW3VdPWxldmVsW3JlbW92ZWRdKzE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgc2MuY2xvc2UoKTsKCX0KfQ==

MTAgOAoxIDIKMSA1CjEgMwoxIDQKMiAxMAo2IDkKNCA2CjMgNg==

10 8
1 2
1 5
1 3
1 4
2 10
6 9
4 6
3 6