No.1777 Kaleidoscope Museum
タグ : / 解いたユーザー数 8
作問者 :
CuriousFairy315
/ テスター :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。