说明

这是一个提交答案题。

21XX 年，JOI 王国面临着一场巨大的危机。JOI 国王主动发起了一项移民计划，将人民迁移到新发现的 IOI 星球。

在 JOI 王国中，有 $N$ 个民族，编号从 1 到 $N$。其中有 $M$ 对民族之间存在着友好关系。在 IOI 星球上，有 $L$ 个居住区，编号从 1 到 $L$（$L \geq N$）。居住区 $i$ 是坐标平面上的点 $P_i(X_i, Y_i)$（$1 \leq i \leq L$）。在移民计划中，我们需要为每个民族分配一个居住区。同一个居住区不能被分配给多个民族。

对于每一对存在友好关系的民族，我们将修建一条连接它们所在居住区的铁路轨道。铁路轨道是连接两个居住区的线段。根据居住区的分配方式，可能会出现两条铁路轨道相交的情况。

应国王的要求，你需要找到一个使得相交的铁路轨道对数最少的移民方案。

任务

给定 JOI 王国的民族信息以及 IOI 星球上居住区的信息，找出一个使得相交的铁路轨道对数最少的移民方案。

输入格式

共有五个子任务。每个子任务对应一个公开的输入数据文件。每个输入数据文件的格式如下。

• 输入的第一行包含两个以空格分隔的整数 $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$ 是坐标平面上的点 $P_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

提示

样例 1 解释

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

:::align{center} :::

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

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

我们将修建如下图所示的多条铁路轨道。相交的铁路轨道对数为 2。

约束条件

所有输入数据满足以下条件。

• $1 \leq A_j \leq N$。
• $1 \leq B_j \leq N$。
• $1 \leq X_i \leq 100\,000$。
• $1 \leq Y_i \leq 100\,000$。
• $P_i, P_j, P_k$ 不共线（$1 \leq i < j < k \leq L$）。
• 对于任意两个民族，我们总可以沿着 IOI 星球上的若干条铁路轨道，从一个民族的居住区旅行到另一个民族的居住区。

:::align{center} :::

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

子任务

对于每个子任务，$N$、$M$、$L$、$S$、$T$ 的值如下表所示。关于 $S$ 和 $T$ 的具体含义，请参见评分细则。

评分细则

这是一个提交答案任务。共有五个子任务，每个子任务包含一个输入数据文件。你需要为每个子任务提交一个对应的输出数据文件。每个子任务的得分计算方式如下：

• 如果你的移民方案不满足题目描述中的条件，则得分为 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。

翻译由 DeepSeek V3.2 完成