In a very close country, Lautaro is in charge of the TUP (Unique Presidential Transmitter), which is responsible for transmitting confidential messages between the government of his country and its neighboring country.
To do this, he has a network of $$$N$$$ stations, numbered from $$$1$$$ to $$$N$$$, where station $$$1$$$ corresponds to his country's government and station $$$N$$$ corresponds to the neighboring country's government. The remaining stations serve the purpose of facilitating message transmission between station $$$1$$$ and station $$$N$$$.
To enable transmissions, there are $$$M$$$ bidirectional links connecting these stations. The $$$i$$$-th of these links allows sending a message between stations $$$A_i$$$ and $$$B_i$$$, with a certain delay of $$$w_i$$$ seconds that has not yet been determined.
Lautaro is calibrating the delays $$$w_i$$$ of this network, which must be integers and sorted in non-decreasing order. That is: $$$1\le w_1\le w_2\le \ldots \le w_M$$$ with $$$w_i \in \mathbb{Z}$$$ for $$$1 \leq i \leq M$$$.
Lautaro wants to minimize the network's efficiency coefficient, which depends on a parameter $$$k$$$ ranging from $$$1$$$ to $$$M$$$. It is computed using the following formula:
$$$$$$\frac{f(w_1, w_2, \ldots, w_M)}{w_1+w_2+\ldots+w_k}$$$$$$
where $$$f(w_1, w_2, \ldots, w_M)$$$ is the minimum time required to send a message from station $$$1$$$ to station $$$N$$$ (possibly using intermediate stations), given that the link delays are $$$w_1, w_2, \ldots, w_M$$$.
Since Lautaro does not yet know which value of $$$k$$$ will be used to compute this coefficient, he will calculate it for all $$$M$$$ integer values of $$$k$$$ between $$$1$$$ and $$$M$$$.
Your task is to help Lautaro and find, for each integer value of $$$k$$$ with $$$1\le k \le M$$$, the infimum of the network's efficiency coefficient across all possible integer delays satisfying $$$1\le w_1 \le w_2 \le \ldots \le w_M$$$.
The infimum of a set $$$S$$$ is the greatest value $$$c$$$ such that $$$x\ge c$$$ for all $$$x\in S$$$. For example, the infimum of the set $$$\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\ldots\}$$$ is $$$0$$$, the infimum of the set $$$\{x \mid 1 \lt x \lt 3\}$$$ is $$$1$$$, and the infimum of the set $$$\{7,13,22\}$$$ is $$$7$$$. Only in the third set the infimum is also a minimum, since in the other two the infimum does not belong to the set.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 5000$$$, $$$1 \leq M \leq 5000$$$), the number of stations and the number of links.
The $$$i$$$-th of the following $$$M$$$ lines contains two integers $$$A_i$$$ and $$$B_i$$$ ($$$1\le A_i, B_i\le N$$$, $$$A_i\ne B_i$$$), the stations connected by the $$$i$$$-th link. There may be multiple links connecting the same pair of stations.
It is guaranteed that it is possible to send a message from station $$$1$$$ to station $$$N$$$, possibly using intermediate stations.
$$$M$$$ lines, where the $$$i$$$-th line contains the infimum of the network's efficiency coefficient for $$$k=i$$$.
For each value, your output will be accepted if its absolute or relative error is at most $$$10^{-6}$$$.
Formally, let your output be $$$a$$$ and the jury's answer be $$$b$$$, your answer will be accepted if $$$\frac{\vert{}a-b\vert{}}{\max(1,\vert{}b\vert{})}\le 10^{-6}$$$.
4 41 22 33 12 4
2 1 0.5 0.3333333
2 11 2
1
The following image corresponds to the TUP network for the first example:
For $$$k=1$$$ and $$$k=2$$$, the minimum of the network's efficiency coefficient is achieved with $$$w_1=w_2=w_3=w_4=2$$$ (which is also the infimum). Here $$$f(2,2,2,2)=4$$$, since it is the minimum time required to send a message from station $$$1$$$ to station $$$4$$$ along the path $$$1\to 2\to 4$$$ with a total delay of $$$w_1+w_4=2+2=4$$$. In the first case, we divide by $$$w_1=2$$$, and in the second case by $$$w_1+w_2=2+2=4$$$.
For $$$k=3$$$, it can be shown that the infimum is $$$\frac{1}{2}$$$, but it is not a minimum because that value cannot be achieved.
