408357: GYM103104 H Information Transmission

There are $$$N$$$ stations of SERN in Akihabara, numbered $$$1$$$ through $$$N$$$. Now SERN want to transfer a set of messages about Rintaro's time machine from station $$$1$$$ to other stations. But because each station has a different broadcasting power, the signal may need to be relayed several times to reach each station. Specifically, all the sites form a directed graph, where an edge from $$$X$$$ to $$$Y$$$ indicates that $$$X$$$ can transmit a signal to site $$$Y$$$. In each transmission process, the signal will occur attenuation, resulting in a part of the information get lost. However, if a message sent by a station is picked up by the station itself with decays up to $$$\textbf{three}$$$ times after it is sent, then we believe that the loop through which the message travels is capable of self-correcting. Each path along the entire loop that has the ability to self-correct will not generate signal attenuation.

Now SERN wants to know the minimum number of decays that a message from station $$$1$$$ has to go through before it reaches each of these stations.

The first line has two integers $$$N,M \; (1 \leq N \leq 300, 0 \leq M \leq 10000)$$$, representing the number of stations and transitive relationships.

In the following $$$m$$$ lines, two numbers $$$X$$$ and $$$Y$$$ in each line, representing that station $$$X$$$ can transmit information to station $$$Y$$$.

It's guaranteed that the graph doesn't contain any multi edges or self loops.

Output one line containing $$$N$$$ numbers, the $$$i^{\rm{th}}$$$ number represents the times of attenuation the information needs to go through from station $$$1$$$ to station $$$i$$$. If a site cannot receive the information from station $$$1$$$, please output $$$-1$$$ instead.

8 11
1 2
2 5
2 3
3 5
3 4
4 5
5 1
4 6
6 7
7 8
8 6

0 0 0 0 0 1 1 1