21世纪，JOI王国面临着巨大的危机。JOI王国的国王决定带头将国民迁移到最近发现的IOI星上。

在JOI王国中，有 $N$ 个民族，编号为 $1$ 到 $N$。有 $M$ 对民族之间存在友好关系。在IOI星上，有 $L$ 个居住区，编号为 $1$ 到 $L$ ($L \ge N$)。居住区 $i$ 是坐标平面上的点 $P_i(X_i, Y_i)$ ($1 \le i \le L$)。在迁移项目中，我们将为每个民族分配一个居住区。每个居住区最多只能分配给一个民族。

对于每一对有友好关系的民族，我们将在它们各自的居住区之间修建一条铁轨。铁轨是连接两个居住区的线段。根据居住区的分配方式，两条铁轨可能会相交。

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

题目描述

给定JOI王国的民族信息和IOI星上的居住区信息，找到一个迁移方案，使得相交的铁轨对数最少。

输入格式

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

• 第一行包含两个空格分隔的整数 $N$ 和 $M$。这表示JOI王国中有 $N$ 个民族，且有 $M$ 对民族之间存在友好关系。
• 接下来的 $M$ 行中，第 $j$ 行 ($1 \le j \le M$) 包含两个空格分隔的整数 $A_j$ 和 $B_j$。这表示民族 $A_j$ 和民族 $B_j$ 之间存在友好关系。
• 接下来的一行包含一个整数 $L$，表示IOI星上的居住区数量。
• 接下来的 $L$ 行中，第 $i$ 行 ($1 \le i \le L$) 包含两个空格分隔的整数 $X_i$ 和 $Y_i$。这表示居住区 $i$ 在坐标平面上的位置为 $P_i(X_i, Y_i)$。

输出格式

对于每个输入数据文件，提交一个输出数据文件。输出数据文件包含 $N$ 行。第 $k$ 行 ($1 \le k \le N$) 包含一个整数，表示分配给民族 $k$ 的居住区编号。

数据范围

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

• $1 \le A_j \le N$。
• $1 \le B_j \le N$。
• $1 \le X_i \le 100\,000$。
• $1 \le Y_i \le 100\,000$。
• $P_i, P_j, P_k$ 不共线 ($1 \le i < j < k \le L$)。
• 对于任意两个民族，可以通过IOI星上的铁轨从一个民族的居住区到达另一个民族的居住区。

子任务

对于每个子任务，$N, M, L, S, T$ 的值如下表所示。关于 $S, T$ 的值，请参阅评分说明。

评分

这是一个仅输出答案的任务。共有五个子任务，每个子任务包含一个输入数据文件。请为每个子任务提交一个输出数据文件。每个子任务的得分计算如下：

• 如果你的迁移方案不满足题目描述中的条件，得分为 0。
• 如果你的迁移方案满足题目描述中的条件，得分根据 $S, T$ 的值计算。设 $C$ 为相交的铁轨对数。
  • 如果 $T < C$，得分为 0。
  • 如果 $S < C \le T$，得分为 $\lfloor 1 + 19 \times (\frac{T - C}{T - S})^2 \rfloor$。其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
  • 如果 $C \le S$，得分为 20。

说明

根据居住区的分配方式，可能会出现超过两条铁轨在同一点相交的情况。

样例

样例输入 1

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

1
5
4
2
7
3

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

共有六个民族。我们按如下方式为每个民族分配居住区：

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

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

• 连接居住区 1（民族 1 的位置）和居住区 4（民族 3 的位置）的铁轨，与连接居住区 2（民族 4 的位置）和居住区 3（民族 6 的位置）的铁轨相交。
• 连接居住区 1（民族 1 的位置）和居住区 4（民族 3 的位置）的铁轨，与连接居住区 2（民族 4 的位置）和居住区 5（民族 2 的位置）的铁轨相交。