LCC '22 Contest 6 S3 - The Kirby Shows

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type

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?


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


There are no comments at the moment.