問題一覧 > 通常問題

No.1451 集団登校

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 43
作問者 : CaliforniumerCaliforniumer / テスター : shiomusubi496shiomusubi496
1 ProblemId : 6098 / 出題時の順位表
問題文最終更新日: 2021-03-31 15:10:37

問題文

$N$ 人の生徒が集団で学校に登校します。生徒は家から出た時点では $N$ 人全員が自分 $1$ 人のみの班の班長ですが、続々と班と班が合流していきます。

$i$ 回目の班の合流は $2$ つの整数 $a_i,b_i$ で与えられ、これは $a_i$ 番目の生徒が所属する班と $b_i$ 番目の生徒が所属する班が合流することを表します。(同じ班の人同士が与えられた場合、何も起こりません)。

$2$ つの班が合流した時、班は $1$ つになり、新しくできた班の班長は $2$ つの班のうち人数が多かった方の班の班長が引き継ぎます。(班長は $1$ つの班につき必ず $1$ 人です。) $2$ つの班の人数が同じだった場合はランダムにどちらかの班の班長が新しい班の班長になります。

なお、班の合流は必ず $i$ の昇順に行われます。(15:10 追記)

$M$ 回の合流を終えた時に $i$ 番目の生徒 ($1\leq i\leq N$) についてその生徒が班長である確率を注釈で述べるように $mod\ 10^9+7$ で求めてください。

なお、最終的に複数班が存在する可能性もあるため、最終的な班長の数は一人とは限りません。

注釈

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。ここで、 $x,y$ は整数であり、 $x$ は $10^9+7$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。

そして、 $xz\equiv y(mod\ 10^9+7)$ を満たすような $0$ 以上 $10^9+6$ 以下の唯一の整数 $z$ を出力してください。

入力

$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$
  • 入力は全て整数

出力

$N$ 行に渡って出力してください。

$i$ 行目には、 $i$ 番目の生徒が最終的に班長である確率を注釈に従って出力してください。

サンプル

サンプル1
入力
4 3
1 2
3 4
1 3
出力
250000002
250000002
250000002
250000002

それぞれの生徒が最終的に班長である確率は全員 $\frac{1}{4}$ です。

サンプル2
入力
7 5
1 2
3 5
4 7
2 6
3 7
出力
500000004
500000004
250000002
250000002
250000002
0
250000002

サンプル3
入力
30 1
7 25
出力
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

$7$ 番目の生徒と $25$ 番目の生徒が最終的に班長である確率はそれぞれ $\frac{1}{2}$ で、それ以外の生徒は最終的に必ず班長です。

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