给定一个连通图的平面嵌入。图的每个顶点对应一个具有整数坐标的不同点。每条连接两个顶点的边对应连接这两个对应点的线段。由于给定的嵌入是平面的，对应于边的线段除了它们的公共端点外不共享任何点。给定的嵌入经过组织，使得所有线段的倾角都是 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|$ 之一。

图 H.1. 样例输入 1 和 2

你的任务是用四种颜色 $\{1, 2, 3, 4\}$ 中的一种为每个顶点着色，使得没有两个由边连接的顶点具有相同的颜色。根据著名的四色定理，这样的着色总是可能的。请找到其中一种。

输入格式

输入包含单个测试用例，格式如下：

$n$ $m$ $x_1$ $y_1$ $\vdots$ $x_n$ $y_n$ $u_1$ $v_1$ $\vdots$ $u_m$ $v_m$

第一行包含两个整数 $n$ 和 $m$。$n$ 是顶点数，$m$ 是边数，满足 $3 \le n \le m \le 10\,000$。顶点编号为 $1$ 到 $n$。接下来的 $n$ 行中，每行包含两个整数。第 $v$ 行的整数 $x_v$ ($0 \le x_v \le 1000$) 和 $y_v$ ($0 \le y_v \le 1000$) 表示对应于顶点 $v$ 的点的坐标。顶点对应于不同的点，即对于 $u \neq v$，$(x_u, y_u) \neq (x_v, y_v)$ 成立。接下来的 $m$ 行中，每行包含两个整数。第 $i$ 行的整数 $u_i$ 和 $v_i$（满足 $1 \le u_i < v_i \le n$）表示存在一条连接顶点 $u_i$ 和 $v_i$ 的边。

输出格式

输出应包含 $n$ 行。输出的第 $v$ 行应包含一个整数 $c_v \in \{1, 2, 3, 4\}$，表示顶点 $v$ 被染成颜色 $c_v$。对于图中连接 $u$ 和 $v$ 的每一条边，输出必须满足 $c_u \neq c_v$。如果存在多种解，你可以输出其中任意一种。

样例

样例输入 1

5 8
0 0
2 0
0 2
2 2
1 1
1 2
1 3
1 5
2 4
2 5
3 4
3 5
4 5

样例输出 1

1
2
2
1
3

样例输入 2

6 10
0 0
1 0
1 1
2 1
0 2
1 2
1 2
1 3
1 5
2 3
2 4
3 4
3 5
3 6
4 6
5 6

样例输出 2

1
2
3
4
2
1