Scenic Area Shortest Path

You are given a tourist attraction area consisting of \(N\) scenic spots numbered from 1 to \(N\). The scenic spot numbered \(N\) is the Tourist Service Center. There are \(M\) bidirectional routes, each connecting two scenic spots.

Given the numbers \(N\) and \(M\) along with the connection information for the \(M\) routes, your task is to compute the minimum number of routes required for each scenic spot \(i\) (for \(1 \leq i \leq N-1\)) to reach the Tourist Service Center (spot \(N\)). If a scenic spot cannot reach the Tourist Service Center, output \(-1\) for that spot.

Example:

• Input: \(N=5\), \(M=4\)
• Routes: 1 \(\leftrightarrow\) 2, 1 \(\leftrightarrow\) 3, 2 \(\leftrightarrow\) 4, 2 \(\leftrightarrow\) 5

The minimum number of routes to reach the Tourist Service Center (spot 5) are as follows:

• From spot 1: 2 routes
• From spot 2: 1 route
• From spot 3: 3 routes
• From spot 4: 2 routes

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

Each of the following \(M\) lines contains two integers \(u\) and \(v\), indicating that there is a bidirectional route connecting scenic spots \(u\) and \(v\).

outputFormat

Output \(N-1\) lines. The \(i\)-th line (for \(1 \leq i \leq N-1\)) should contain the minimum number of routes required to reach the Tourist Service Center (spot \(N\)) from scenic spot \(i\). If scenic spot \(i\) cannot reach the Tourist Service Center, output \(-1\).

sample

5 4
1 2
1 3
2 4
2 5

2
1
3
2