题目描述

译自 JOI Open 2014 Day2 T1「移住計画 / Project of Migration」

在 21XX 年，JOI 王国面临着一场大危机。JOI 王国的国王想要让人民迁移到最近发现的一颗星球 IOI 星。

在 JOI 王国，有 $N$ 个民族，从 $1$ 到 $N$ 编号。有 $M$ 对民族之间有友好关系。在 IOI 星上，有 $L$ 个居住区，从 $1$ 到 $L\ (L \geq N)$ 编号。居住区 $i\ (1 \leq i \leq L)$ 位于坐标平面上的点 $P_i$，$P_i$ 的位置是 $(X_{i}, Y_{i})$。在迁移计划中，我们会给每个民族分配一个居住区。没有一个居住区被分配给多个民族。

对于每一对有友好关系的民族，我们将建造一条连接他们居住区的铁路轨道。铁路轨道是连接两个居住区的线段。根据居住区分配的方式，可能会发生两条铁路轨道相交的情况。

给定 JOI 王国的民族信息和 IOI 星上的居住区信息，你需要找到一个迁移计划，使得最小化铁路轨道相交对数尽可能小。

注意：根据居住区分配的方式，可能会有多于两条铁路轨道在一个点相交的情况。

输入格式

本题共 $5$ 组数据。

每组数据的的第一行包含两个用空格分隔的整数 $N$ 和 $M$，表示 JOI 王国有 $N$ 个民族，有 $M$ 对民族之间有友好关系。

接下来的 $M$ 行中的第 $j\ (1 \leq j \leq M)$ 行包含两个用空格分隔的整数 $A_{j}$ 和 $B_{j}$，表示民族 $A_{j}$ 和民族 $B_{j}$ 有友好关系。

接下来的一行包含一个整数 $L$，表示 IOI 星上的居住区数量。

接下来的 $L$ 行中的第 $i\ (1 \leq i \leq L)$ 行包含两个用空格分隔的整数 $X_{i}$ 和 $Y_{i}$，表示居住区 $i$ 是坐标平面上的点 $(X_{i}, Y_{i})$。

输出格式

输出 $N$ 行。第 $k\ (1 \leq k \leq N)$ 行包含一个整数，表示分配给民族 $k$ 的居住区。

6 10
1 2
1 3
1 4
1 5
1 6
2 4
2 6
3 4
3 5
4 6
7
2 1
2 5
4 3
6 7
7 3
8 5
9 1

1
5
4
2
7
3

在这个样例中，IOI 星上有七个居住区，如下图所示。

有六个民族。我们给每个民族分配一个居住区，如下：

• 给民族 $1$ 分配居住区 $1$。
• 给民族 $2$ 分配居住区 $5$。
• 给民族 $3$ 分配居住区 $4$。
• 给民族 $4$ 分配居住区 $2$。
• 给民族 $5$ 分配居住区 $7$。
• 给民族 $6$ 分配居住区 $3$。

我们按照下图所示建造铁路轨道。铁路轨道相交的对数是 $2$。

• 连接居住区 $1$（民族 $1$ 的地方）和居住区 $4$（民族 $3$ 的地方）的铁路轨道和连接居住区 $2$（民族 $4$ 的地方）和居住区 $3$（民族 $6$ 的地方）的铁路轨道相交。
• 连接居住区 $1$（民族 $1$ 的地方）和居住区 $4$（民族 $3$ 的地方）的铁路轨道和连接居住区 $2$（民族 $4$ 的地方）和居住区 $5$（民族 $2$ 的地方）的铁路轨道相交。

计分

对于每个输出文件，您的分数将以以下方式计算：

• 如果你的迁移计划不满足题目描述中的条件，你的分数是 $0$。
• 如果你的迁移计划满足题目描述中的条件，你的分数根据 $S, T$ 的值如下计算。设 $C$ 为铁路轨道相交对数。
• 如果 $T<C$，你的分数是 $0$。
• 如果 $S<C \leq T$，你的分数是 $\left\lfloor 1+19 \times\left(\frac{T-C}{T-S}\right)^{2}\right\rfloor$。这里，$\lfloor x\rfloor$ 表示不大于 $x$ 的最大整数。
• 如果 $C \leq S$，你的分数是 $20$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq A_{j} \leq N$
• $1 \leq B_{j} \leq N$
• $1 \leq X_{i} \leq 10^5$
• $1 \leq Y_{i} \leq 10^5$
• $P_{i}, P_{j}, P_{k}$ 不共线 $(1 \leq i<j<k \leq L)$
• 对于任意两个民族，我们可以通过在 IOI 星上的一些铁路，从一个民族的居住区到达另一个民族的居住区

对于每个测试点，$N, M, L, S, T$ 的值如下表所示。关于 $S, T$ 的值，参见计分。