Minimum Travel Time

You are given a graph representing cities and roads. The graph consists of n cities numbered from 1 to n and m bidirectional roads. Each road connects two different cities. Starting from city 1, your task is to determine the minimum travel time (i.e., the minimum number of roads to traverse) required to reach every other city.

Formally, consider a graph \(G = (V, E)\) with \(|V| = n\) and \(|E| = m\). For each city \(i\) where \(2 \le i \le n\), compute the minimum number of edges on any path from city 1 to city \(i\). If a city is unreachable from city 1, output \(-1\) for that city.

Input is provided via standard input and output should be printed to standard output.

inputFormat

The first line contains two integers (n) and (m), representing the number of cities and roads respectively. The next (m) lines each contain two integers (u) and (v), indicating that there is a road connecting city (u) and city (v).

outputFormat

Output a single line containing (n-1) space-separated integers. The (i)-th integer represents the minimum travel time (i.e., the minimum number of roads) required to travel from city 1 to city (i+1). If a city is unreachable, output (-1) for that city.## sample

6 7
1 2
1 3
2 4
3 4
4 5
3 5
5 6

1 1 2 2 3