#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);
	vector<int> ways(n, 0);
	queue<int> q;
	q.push(source);
	visited[source]=1;
	ways[source]=1;
	while(!q.empty()){
		int node=q.front();
		q.pop();
		visited[node]=1;
		for(auto adjNode : adjList[node]){
			if(!visited[adjNode]){
				//first time visit
				visited[adjNode]=1;
				level[adjNode]=level[node]+1;
				ways[adjNode]=ways[node];
				q.push(adjNode);
			}
			else{
				if(level[adjNode]==level[node]+1){
					//node adjNode is on shortest path
					ways[adjNode]=ways[adjNode]+ways[node];
				}
				else{
					//node adjNode is not on the shortest path
					//no need to count
				}
			}
		}
	}
	for(int i=0;i<ways.size();i++){
		cout<<"node "<<i<<" : "<<ways[i];
		cout<<"\n";
	}
	return 0;
}