402221: GYM100703 D Draconian Actions

— And what about knights who rescue princesses? Is it also just a game? — Princess seemed to be disappointed.

— Well... If a princess and a knight have taken to each other, why hinder them? — Dragon felt a sympathy for Princess, and regretted for making her upset.

As a matter of fact, Dragon agreed with the literary classic who wrote "happy families are all alike". Long ago he counted all knights and princes in surrounding castles, and there were exactly n of them, as many as princesses. In Dragon's opinion, they needed to be acquainted with each other.

He shared these considerations with Princess and told her that he wants to offer to all knights, all princes and all princesses to make lists of preferences. In the first place of every list there should be written the name of the person, marriage with whom, he or she believes, makes her or him most happy. In the second place there should be written the name of the person, marriage with whom, he or she believes, makes her or him most happy, if marriage with the person in the first place is impossible, and so on. Every list must consist of n candidates.

After all the lists are made, all the people are divided into pairs. We call a set of such pairs a matching. Each person r₁ wishes that every person r₂ who is more preferable than who r₁ is married, married someone, who is in r₂'s opinion better than r₁. We call a set of such pairs a stable matching.

Let's describe it formally. Consider two pairs (m₁, f₁) and (m₂, f₂). Assume, that m₂ prefers f₁ over f₂ (i.e. an index of f₁ is less than index of f₂ in the list of m₂). But f₁ believes that m₁ is better choice than m₂ (i.e. an index of m₁ is less than index of m₂ in the list of f₁)

Otherwise the matching would not be stable, because f₁ and m₂ could form a pair with each other.

Then Princess doubted everyone will be happy in this case: for example there can be a pair of people where each single person put other one in end of his list.

Of course, Dragon has already thought about this and proposed to introduce a characteristics called dissatisfaction. A dissatisfaction of a person r is defined as his or her partner's number in r's list. A dissatisfaction of a matching is a maximum dissatisfaction amongst people in the matching.

You are given lists of preferences for all people, and you are to find a stable matching with minimum possible dissatisfaction.

The first line contains the integer n (1 ≤ n ≤ 200).

Each line of the following n ones contains a list of preferences of some prince or knight — a permutation of numbers from 1 to n.

Each line of the next n ones contains a list of preferences of some princess — a permutation of numbers from 1 to n.

Consider that princes and knights, as well as princesses, numbered in the order they appear in the input.

In the first line print the only integer — minimum possible dissatisfaction of a matching described above.

In the second line print n integers p_j — the matching itself, where p_j is the number of princess who marries prince or knight #j.

If multiple answers exist, choose any of them.

4
3 4 1 2
3 2 4 1
4 2 1 3
2 1 3 4
3 1 2 4
2 3 4 1
2 3 1 4
4 2 3 1

3
1 3 4 2

Let us explain the sample. Let us show that result matching is stable.

Consider pair (1, 1). The first partner's list of preferences contains 1 at position #3. The first partner would be happy to be in pair with 3 (first position in his list) or 4 (if 3 does not want to be in pair with him). The second partner's list of preferences contains 1 at position 2, so the second partner would be happy to be in pair with 3.

Thus the pair (2, 3) is optimal.

The first partner in pair (3, 4) is confident in his choice (4 is the first number in his list of preferences). But the second partner would rather change her current partner and be paired with 4 or (if 4 does not want) 2.

The situation in pair (4, 2) is similar to the situation in previous pair. The first partner does not want to change anything, but the second partner would rather leave his current partner in favor of 2 (or 3, if 2 does not want).

Let us analyse the preferences listed above.

The first partner in (1, 1) wants to be with 3, but 3 is paired with 2 already and wants to change nothing. Since that he tries to make pair with 4, though, unsuccessfully, since 4 is paired with 3 already and will not leave the pair in favor of 1. The second partner in (1, 1) tries to make pair with 3, unsuccessfully too because 3 in pair (3, 4) is happy of his pair.

The second partner in (3, 4) would like to change his current partner, but his desired 4 and 2 have already made their better choices.

The second partner in (4, 2) will be refused by desired 2 and 3 (from (2, 3) and (3, 4) pairs respectively).

In this matching maximum dissatisfied people are the first partner in pair (1, 1) and the second partners in pairs (3, 4) and (4, 2). Their dissatisfaction is 3.

There is no possible matching with dissatisfaction less than 3. Verify it by brute forcing all possible stable matchings.