問題一覧 > 通常問題

No.2531 Coloring Vertices on Namori

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

問題文

NN 頂点 NN 辺の単純連結無向グラフが与えられます．ii 番目の辺は頂点 uiu_i と頂点 viv_i を双方向に結びます．

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

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

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

制約

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

入力

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

NN KK
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uNu_N vNv_N

出力

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

サンプル

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

頂点 1,2,31, 2, 3 に塗る色を c1,c2,c3c_1, c_2, c_3 とすると，次の 66 通りが条件を満たします．

  • (c1,c2,c3)=(1,2,3)(c_1, c_2, c_3) = (1, 2, 3)
  • (c1,c2,c3)=(1,3,2)(c_1, c_2, c_3) = (1, 3, 2)
  • (c1,c2,c3)=(2,1,3)(c_1, c_2, c_3) = (2, 1, 3)
  • (c1,c2,c3)=(2,3,1)(c_1, c_2, c_3) = (2, 3, 1)
  • (c1,c2,c3)=(3,1,2)(c_1, c_2, c_3) = (3, 1, 2)
  • (c1,c2,c3)=(3,2,1)(c_1, c_2, c_3) = (3, 2, 1)

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

頂点 1,2,3,41, 2, 3, 4 に塗る色を c1,c2,c3,c4c_1, c_2, c_3, c_4 とすると，次の 22 通りが条件を満たします．

  • (c1,c2,c3,c4)=(1,2,1,2)(c_1, c_2, c_3, c_4) = (1, 2, 1, 2)
  • (c1,c2,c3,c4)=(2,1,2,1)(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

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

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