Batrick Lin: overlord of WLMAC, supreme leader, lord over all his student and staff subjects can sometimes seem far beyond mortal comprehension. Nonetheless, his interests often align with those of mankind. One such interest are game shows! Thus, he has decided to capture bring you to his game show and play a little game.

In this game show, there are ~N~ cards numbered ~1~ to ~N~, all face-down. Of these ~N~ cards, you know that one of them contains a kirby character, the rest all contain daggers. You are given ~Q~ turns: on each turn, you pick a card ~A_i~ that is still face-down, and Batrick will flip a random face-down card ~B_i~ apart from the one you chose that contains daggers.

Now, given ~Q~ of these turns, can you figure out the probability that each card from ~1~ to ~N~ contains the kirby?

Constraints

~1\le N\le 10^5~

~1\le Q\le N-1~

~1\le A_i, B_i\le N~

~A_i\ne B_i~

Subtask 1 [30%]

~1\le N\le 1000~.

Subtask 3[70%]

No additional constraints.

Input Specification

The first line contains 2 integers: ~N~, and ~Q~.

The next ~Q~ lines each contain two integers: ~A_i~ and ~B_i~.

Output Specification

One line with ~N~ floating point numbers: the probability that the ~i~-th card is a dagger. Your answer will be considered correct if it has a relative error less than ~10^{-5}~

Sample Input

3 1
1 2

Sample Output

0.333333 0 0.6666667

Sample Explanation

After picking the first card, you know that the second card definitely contains a dagger. If the third card contained a kirby, then the second card would be flipped with ~100\%~ certainty. However, if the first card contained a kirby, then there would only be a ~50\%~ chance the second card was flipped. At the very start, it is equally likely that the first and third cards contain a kirby. Hence, since it is so much more likely that the second card would be picked if the third card was a dagger, you can calculate the probability that the third card contains a kirby as ~\frac{\frac13}{\frac13+\frac13\cdot\frac12}=\frac23\approx 0.6666667~