|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||2||2||1||100.000%|
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 ≥ N). The resident area i is the point Pi(Xi, Yi) in the coordinate plane (1 ≤ i ≤ 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.
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.
There are five subtasks. Each subtask corresponds to a public input data file. The format of each input data file is as follows.
All input data satisfy the following conditions.
For each input data file, submit an output data file. The output data file consists of N lines. The k-th line (1 ≤ k ≤ 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
이 문제는 압축 파일의 02.txt로 채점을 합니다.
It may happen that more than two railway tracks intersect at a point depending on the way of allocation of resident areas.
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.
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.
Sample Input and Output
In this sample input, there are seven resident areas on the IOI star as in the following figure.
There are six ethnic groups. We allocate a resident area to each ethnic group as follows.
We will construct railway tracks as in the following figure. The number of pairs of railway tracks intersecting each other is 2.