이주 계획 Output Only 컴파일 명령

21XX년이 되자, JOI 왕국은 중대한 위기에 직면합니다. JOI 왕국의 왕은 최근 발견된 별인 IOI별로 사람들을 이주하게 할 계획을 세웁니다.

JOI 왕국에는 $1$부터 $N$까지의 번호가 붙은 $N$개의 종족이 있습니다. 친선 관계를 가지는 $M$쌍의 종족 쌍들이 있습니다. IOI 별에는 $1$부터 $L$까지의 번호가 붙은 $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}$번 종족 사이에 친선 관계가 있다는 것을 의미합니다.
• 그 다음 줄에는 IOI별의 거주 지역의 수 $L$이 주어집니다.
• 다음에 $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$의 값에 대해서는 '채점 방식'을 읽어보세요.

채점 방식

이 문제는 Output-only 문제입니다. 다섯 개의 서브태스크가 있으며, 각 서브태스크는 하나의 입력 파일을 포함합니다. 입력 파일은 여기에서 내려받을 수 있습니다. 각 서브태스크에 대해 출력 파일을 제출하세요. 각 서브태스크에 대한 여러분의 점수는 아래와 같이 계산됩니다.

• 만약 여러분의 이주 계획이 문제에서 제시한 조건을 만족하지 않는다면 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점.

제출 방법

01.txt에 대한 출력 파일은 01-out.txt, 02.txt에 대한 출력 파일은 02-out.txt, ... 로 하신 뒤 이들을 모두 하나의 zip 형식의 압축 파일에 넣어 제출해 주세요.

예제 입력 및 출력

이 예제 입력에서, IOI별에는 아래 그림과 같은 7개의 거주 지역이 있습니다.

6개의 종족이 있습니다. 우리는 각 종족에게 아래와 같이 거주 지역을 배정합니다.

• 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번 종족의 장소)을 잇는 철도는 서로 교차합니다.