問題一覧 > 通常問題

No.2531 Coloring Vertices on Namori

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 87
作問者 : AngrySadEightAngrySadEight / テスター : 👑 p-adicp-adic
0 ProblemId : 10237 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-24 15:34:48

問題文

$N$ 頂点 $N$ 辺の単純連結無向グラフが与えられます．$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結びます．

このグラフの頂点のそれぞれに，色 $1, 2, \dots, K$ の $K$ 個の色から $1$ 色を選んで塗ります．ただし，隣接する頂点を同じ色で塗ることはできません．

頂点への色の塗り方の総数を $998244353$ で割った余りを求めてください．

ただし，頂点への色の塗り方は，ある頂点が存在し，その頂点に塗られている色が異なる場合に区別されます．

制約

  • 入力はすべて整数である．
  • $3 \leq N \leq 2 \times 10^5$
  • $2 \leq K \leq 2 \times 10^5$
  • $1 \leq u_i < v_i \leq N$
  • $(u_i, v_i) \neq (u_j, v_j) (i \neq j)$
  • 与えられるグラフは単純かつ連結である．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_N$ $v_N$

出力

頂点への色の塗り方の総数を $998244353$ で割った余りを出力せよ．

サンプル

サンプル1
入力
3 3
1 2
2 3
1 3
出力
6

頂点 $1, 2, 3$ に塗る色を $c_1, c_2, c_3$ とすると，次の $6$ 通りが条件を満たします．

  • $(c_1, c_2, c_3) = (1, 2, 3)$
  • $(c_1, c_2, c_3) = (1, 3, 2)$
  • $(c_1, c_2, c_3) = (2, 1, 3)$
  • $(c_1, c_2, c_3) = (2, 3, 1)$
  • $(c_1, c_2, c_3) = (3, 1, 2)$
  • $(c_1, c_2, c_3) = (3, 2, 1)$

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

頂点 $1, 2, 3, 4$ に塗る色を $c_1, c_2, c_3, c_4$ とすると，次の $2$ 通りが条件を満たします．

  • $(c_1, c_2, c_3, c_4) = (1, 2, 1, 2)$
  • $(c_1, c_2, c_3, c_4) = (2, 1, 2, 1)$

サンプル3
入力
10 200000
1 2
1 3
2 4
2 5
3 9
4 7
5 8
1 10
6 10
7 10
出力
956138134

頂点への色の塗り方の総数を $998244353$ で割った余りを出力してください．

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