Description

In the year of 21XX, the JOI kingdom is faced with a big crisis. The King of the JOI kingdom takes the initiative to migrate people to the IOI star, which is a recently-discovered star.

In the JOI kingdom, there are $N$ ethnic groups numbered from 1 to $N$. There are $M$ pairs of ethnic groups which have friendly relationships. On the IOI star, there are $L$ resident areas numbered from 1 to $L$ ($L \geq N$). The resident area $i$ is the point $P_i(X_i, Y_i)$ in the coordinate plane ($1 \leq i \leq L$). In the migration project, we allocate one of the resident areas to each ethnic group. No resident area is allocated to more than one ethnic groups.

For each pair of ethnic groups having a friendly relationship, we will construct a railway track connecting their resident areas. A railway track is a line segment connecting two resident areas. It may happen that two railway tracks intersect each other depending on the way of allocation of resident areas.

By request from the King, you are to find a migration project with minimum number of pairs of railway tracks intersecting each other.

Task

Given the information of ethnic groups in the JOI kingdom and the information of the resident areas on the IOI star, find a migration project with minimum number of pairs of railway tracks intersecting each other.

Input Format

There are five subtasks. Each subtask corresponds to a public input data file. The format of each input data file is as follows.

• The first line of input contains two space separated integers $N$ and $M$. This means there are $N$ ethnic groups in the JOI kingdom, and there are $M$ pairs of ethnic groups having friendly relationships.
• The $j$-th line ($1 \leq j \leq M$) of the following $M$ lines contains two space separated integers $A_j$ and $B_j$. This means the ethnic group $A_j$ and the ethnic group $B_j$ have a friendly relationship.
• The following line contains an integer $L$, the number of resident areas on the IOI star.
• The $i$-th line ($1 \leq i \leq L$) of the following $L$ lines contains two space separated integers $X_i$ and $Y_i$. This means the resident area $i$ is $P_i(X_i, Y_i)$ in the coordinate plane.

Note

It may happen that more than two railway tracks intersect at a point depending on the way of allocation of resident areas.

Output Format

For each input data file, submit an output data file. The output data file consists of $N$ lines. The $k$-th line ($1 \leq k \leq N$) contains an integer which denotes the resident area allocated to the ethnic group $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

Hint

Sample 1 Explanation

In this sample input, there are seven resident areas on the IOI star as in the following figure.

:::align{center} :::

There are six ethnic groups. We allocate a resident area to each ethnic group as follows.

• We allocate the resident area 1 to the ethnic group 1.
• We allocate the resident area 5 to the ethnic group 2.
• We allocate the resident area 4 to the ethnic group 3.
• We allocate the resident area 2 to the ethnic group 4.
• We allocate the resident area 7 to the ethnic group 5.
• We allocate the resident area 3 to the ethnic group 6.

We will construct railway tracks as in the following figure. The number of pairs of railway tracks intersecting each other is 2.

Constraints

All input data satisfy the following conditions.

• $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$ do not lie in a line ($1 \leq i < j < k \leq L$).
• For any two ethnic groups, we can travel from the resident area of one group to the resident area of another group by passing through some railway tracks on the IOI star.

:::align{center} :::

• The railway track connecting the resident area 1 (the place of the ethnic group 1) and the resident area 4 (the place of the ethnic group 3) and the railway track connecting the resident area 2 (the place of the ethnic group 4) and the resident area 3 (the place of the ethnic group 6) are intersecting each other.
• The railway track connecting the resident area 1 (the place of the ethnic group 1) and the resident area 4 (the place of the ethnic group 3) and the railway track connecting the resident area 2 (the place of the ethnic group 4) and the resident area 5 (the place of the ethnic group 2) are intersecting each other.

Subtasks

For each subtask, the values of $N$, $M$, $L$, $S$, $T$ are as in the following table. For the values of $S$, $T$, see Grading.

Grading

This is an output-only task. There are five subtasks, and each subtask consists of one input data file. Submit an output data file for each subtask. Your score of each subtask is calculated as follows.

• If your migration project does not satisfy the conditions in the task statement, your score is 0.
• If your migration project satisfies the conditions in the task statement, your score is calculated according to the values of $S$, $T$ as follows. Let $C$ be the number of pairs of railway tracks intersecting each other.
  • If $T < C$, your score is 0.
  • If $S < C \leq T$, your score is $\left\lfloor 1 + 19 \times \left( \frac{T - C}{T - S} \right)^2 \right\rfloor$. Here, $\lfloor x \rfloor$ denotes the largest integer less than or equal to $x$.
  • If $C \leq S$, your score is 20.