## Yet Another Contest 7 P3 - No More Math Homework

View as PDF

Points: 12 (partial)
Time limit: 3.0s
Python 5.0s
Memory limit: 512M

Author:
Problem type

Long gone are the days of math homework. Now that the final year of school is beginning, students are expected to do their own independent study of their subjects instead. To help them study, the students will be grouped into study groups.

There are students labelled from to , and subjects labelled from to . Each student will be allocated to exactly one study group, denoted by a single positive integer. Recently, researchers have discovered that if a student studies subject on one day, then it is optimal for that student to study subject on the following day. Hence, the students have made the following plan: on day , the -th student will study subject . Then, if student studied subject on day , they will study subject on day . This continues indefinitely.

At the end of each day, the students in each study group will meet and share the information they learnt about the subject they studied that day. To reinforce learnt material, on each day, and for each subject, the students who studied that subject on that day should belong to the same study group. Study groups must not change on any day.

As the principal, you wish for there to be as many study groups as possible. To maximise the number of study groups, you have enough influence to make one adjustment plan: you may choose two integers and and set to .

Can you determine the optimal adjustment to the plan, and an optimal allocation of students to study groups?

If the adjustment to the plan is not optimal, but the allocation of students to study groups is optimal for the chosen plan, you will receive % of the points.

#### Input Specification

The first line contains a single integer, .

The second line contains space-separated integers, .

#### Output Specification

On the first line, output two space-separated integers, and , representing the chosen adjustment to the plan. It is possible that already equals , in which case the plan is not adjusted.

On the second line, output space-separated integers. The -th integer represents the study group which the -th student is allocated to. All integers should be between and (inclusive), and the number of unique integers should be maximised for the chosen plan.

#### Sample Input

4
2 3 4 3

#### Sample Output

2 1
1 2 3 4

#### Explanation

If no adjustment to the plan is made, it can be shown that at most two study groups can be formed, as demonstrated by the table below. Students and can form one study group, and students and can form another study group. It can be shown that on every day, for each subject, the students who studied that subject belong to the same study group.

DayStudent 's subjectStudent 's subjectStudent 's subjectStudent 's subject

When the adjustment to plan is made, all four students can be in their own separate study group.