問題一覧 > 通常問題

No.1451 Walking to School in Groups

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 72
作問者 : Californiumer / テスター : shiomusubi496
お気に入りにしたユーザー ProblemId : 6098 / 自分の提出
問題文最終更新日: 2021-03-31 15:10:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
新入生プログラミングコンテスト 2021(昼の部) (順位表) の他の問題:

Problem Statement

$N$ students go to school in groups. When they leave home, all $N$ students are each the leader of a group consisting of only themselves, $1$ person, but groups then merge one after another.

The $i$-th merge is given by $2$ integers $a_i,b_i$, which means that the group to which the $a_i$-th student belongs and the group to which the $b_i$-th student belongs merge. (If the two students are in the same group, nothing happens.)

When $2$ groups merge, they become $1$ group, and the leader of whichever of the $2$ groups had more members takes over as the leader of the new group. (There is always exactly $1$ leader per $1$ group.) If the $2$ groups have the same number of members, the leader of one of the groups, chosen at random, becomes the leader of the new group.

The merges are always performed in ascending order of $i$. (Added at 15:10)

After the $M$ merges have finished, for each $i$-th student ($1\leq i\leq N$), find the probability that the student is a leader, $mod\ 10^9+7$, as described in the Notes.

Note that multiple groups may exist at the end, so the final number of leaders is not necessarily one.

Notes

To output a rational number, first represent it as a fraction $\frac{y}{x}$. Here, $x,y$ are integers, and $x$ must not be divisible by $10^9+7$ (under the constraints of this problem, such a representation is always possible).

Then, output the unique integer $z$ between $0$ and $10^9+6$, inclusive, such that $xz\equiv y(mod\ 10^9+7)$.

Input

$N\ M$
$a_1\ b_1$
$a_2\ b_2$
$a_3\ b_3$
 $\vdots$
$a_M\ b_M$
  • $1\leq N\leq 10^5$
  • $0\leq M\leq 10^5$
  • $1\leq a_i < b_i \leq N$
  • All input values are integers.

Output

Output over $N$ lines.

On the $i$-th line, output the probability that the $i$-th student is finally a leader, in the format described in the Notes.

Sample

Sample 1
Input
4 3
1 2
3 4
1 3
Output
250000002
250000002
250000002
250000002

The probability that each student is finally a leader is $\frac{1}{4}$ for everyone.

Sample 2
Input
7 5
1 2
3 5
4 7
2 6
3 7
Output
500000004
500000004
250000002
250000002
250000002
0
250000002

Sample 3
Input
30 1
7 25
Output
1
1
1
1
1
1
500000004
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
500000004
1
1
1
1
1

The $7$-th student and the $25$-th student are each finally a leader with probability $\frac{1}{2}$, and every other student is always finally a leader.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。