問題一覧 > 通常問題

No.1777 Kaleidoscope Museum

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : CuriousFairy315 / テスター : ramdos
お気に入りにしたユーザー ProblemId : 7273 / 自分の提出
問題文最終更新日: 2021-12-25 23:40:50
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
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

The Kaleidoscope Museum in the country of yuki is shaped as a perfectly circular room inside a perfectly circular room, and pillars stand at the positions dividing the inner circle into $N$ equal parts.
The inner room is partitioned by $M$ walls, and the $i$-th wall connects pillars $u_i$ and $v_i$ in a straight line.
The director, Mr. 315, wants to paint this museum colorfully.
Specifically, he wants every room and every pillar to have a color, with adjacent rooms and pillars painted in different colors.
However, paint gets more expensive as the number of kinds increases, so he wants to use as few colors as possible.
What is the minimum number of colors needed to paint the museum colorfully so that the condition is satisfied?

▼Conditions for being painted in different colors Two pillars are considered adjacent when they are next to each other via a wall or the circumference.
Two rooms are considered adjacent when they are next to each other across a wall or the circumference.
A pillar and a room are considered adjacent when the pillar and the room are next to each other.
Adjacent pillars and rooms must have different colors.
Please also refer to the figures in the samples.

This problem statement can be rephrased as follows.
For the given graph $G$ with $N$ vertices and $N+M$ edges, find $\chi_{vf}(G)$.

Input

$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$
  • There is no wall $i$ such that $(u_i, v_i) = (1, N)$
  • There is no pair $(i, j)$ such that $u_i < u_j < v_i < v_j$
    That is, walls do not cross each other
  • There is no pair $(i, j)$ such that $(u_i, v_i) = (u_j, v_j)$
    That is, the graph has no multiple edges or loops

Output

Output the minimum number of colors needed to paint so that the condition is satisfied.
End the output with a newline.

Sample

Sample 1
Input
3 0
Output
5

The museum is painted as follows.

Sample 2
Input
12 4
1 4
4 7
7 10
1 10
Output
4

The museum is painted as follows.

Sample 3
Input
9 3
1 4
4 7
1 7
Output
4

The museum is painted as follows.

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