問題一覧 > 通常問題

No.1777 万華鏡美術館

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : CuriousFairy315CuriousFairy315 / テスター : ramdosramdos
3 ProblemId : 7273 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-25 23:40:50

問題文

yuki国にある万華鏡美術館は真円状の部屋の中に真円状の部屋がある形になっており、内側の円を $N$ 等分する位置に柱が立っています。
内側の部屋は $M$ 本の壁によって仕切られており、 $i$ 番目の壁は柱 $u_i$ と $v_i$ を一直線に繋いでいます。
館長の315さんはこの美術館をカラフルに塗りたいと考えています。
具体的には、どの部屋及び柱も色が付いており、隣接する部屋及び柱は異なる色で塗られている状態にしたいです。
しかし、塗料は種類が増えるほど値段が高くなるので、なるべく使う色は少なくしたいです。
最低何色の色があれば美術館を条件を満たすようにカラフルに塗れますか？

▼異なる色で塗られる条件 各柱は、壁あるいは円周を用いて隣り合っているときに隣接しているものとします。
また、各部屋は、壁あるいは円周を挟んで隣り合っているときに隣接しているものとします。
柱と部屋は、柱と部屋が隣り合っているときに隣接しているものとします。
そして、隣接している柱及び部屋は異なる色である必要があります。
サンプルの図も参考にしてください。

この問題文は以下のように言い換えることができます。
与えられた $N$ 頂点 $N+M$ 辺のグラフ $G$ に対して、 $\chi_{vf}(G)$ を求めよ。

入力

$N$ $M$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$

  • $3 \leq N \leq 500$
  • $0 \leq M \leq 10^5$
  • $1 \leq u_i < v_i \leq N$
  • $u_i + 2 \leq v_i$
  • $(u_i, v_i) = (1, N)$ となるような壁 $i$ は存在しない
  • $u_i < u_j < v_i < v_j$ となるような組 $(i, j)$ は存在しない
    すなわち、壁同士が交差することはない
  • $(u_i, v_i) = (u_j, v_j)$ となるような組 $(i, j)$ は存在しない
    すなわち、グラフは多重辺もループも持たない

出力

条件を満たすように塗る色数の最小値を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 0
出力
5

美術館は以下の様に塗られます。

サンプル2
入力
12 4
1 4
4 7
7 10
1 10
出力
4

美術館は以下の様に塗られます。

サンプル3
入力
9 3
1 4
4 7
1 7
出力
4

美術館は以下の様に塗られます。

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