P14900 [ICPC 2018 Yokohama R] Four-Coloring
题目描述
给定一个连通图的平面嵌入。图中的每个顶点对应于一个具有整数坐标的不同点。两个顶点之间的每条边对应于连接这两个顶点对应点的直线段。由于给定的嵌入是平面的，对应边的线段除公共端点外不共享任何点。给定的嵌入被组织成使得所有线段的倾斜度都是 $45$ 度的倍数。换句话说，对于存在边的两个顶点 $u$ 和 $v$，其对应坐标分别为 $(x_u, y_u)$ 和 $(x_v, y_v)$，则满足 $x_u = x_v$、$y_u = y_v$ 或 $|x_u - x_v| = |y_u - y_v|$ 中的一个。
:::align{center}
图 H.1. 样例输入 1 和 2
:::
你的任务是为每个顶点涂上四种颜色 $\{1, 2, 3, 4\}$ 中的一种，使得有边连接的两个顶点颜色不同。根据著名的四色定理，这样的着色总是可能的。请找出一种着色方案。
输入格式
输入包含单个测试用例，格式如下。
$$
\begin{aligned}
& n \; m \\
& x_1 \; y_1 \\
& \vdots \\
& x_n \; y_n \\
& u_1 \; v_1 \\
& \vdots \\
& u_m \; v_m
\end{aligned}
$$
第一行包含两个整数 $n$ 和 $m$。$n$ 是顶点数，$m$ 是边数，满足 $3 \leq n \leq m \leq 10\,000$。顶点编号为 $1$ 到 $n$。接下来的 $n$ 行中，每行包含两个整数。第 $v$ 行的整数 $x_v$ （$0 \leq x_v \leq 1000$）和 $y_v$ （$0 \leq y_v \leq 1000$）表示顶点 $v$ 对应点的坐标。顶点对应于不同的点，即对于 $u \neq v$，满足 $(x_u, y_u) \neq (x_v, y_v)$。接下来的 $m$ 行中，每行包含两个整数。第 $i$ 行的整数 $u_i$ 和 $v_i$，满足 $1 \leq u_i < v_i \leq n$，表示存在一条连接顶点 $u_i$ 和 $v_i$ 的边。
输出格式
输出应由 $n$ 行组成。输出的第 $v$ 行应包含一个整数 $c_v \in \{1, 2, 3, 4\}$，表示顶点 $v$ 将被涂色为 $c_v$。输出必须满足对于图中每条连接 $u$ 和 $v$ 的边，都有 $c_u \neq c_v$。如果有多个解，你可以输出其中任意一个。