D. Драконовские меры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

— А как же рыцари, которые спасают принцесс? Они тоже понарошку? — Принцесса выглядела грустной.

— Ну... если принцесса и рыцарь понравились друг другу, зачем же мешать этому? — Дракон успел проникнуться симпатией к Принцессе, и ему было жаль, что он огорчил её.

Вообще-то Дракон полагал, что классик, утверждавший, что «все счастливые семьи похожи друг на друга», был определённо прав. Он уже давно подсчитал, что в сумме принцев в окрестных замках и рыцарей ровно n. А это столько же, сколько и принцесс — если сложить тех, кто проживает в замках, и тех, кто ищет своё счастье, странствуя. И, по его мнению, надо просто правильно перезнакомить их друг с другом.

Он поделился этими соображениями с Принцессой и рассказал ей, что предложил бы каждому рыцарю или принцу и каждой принцессе составить список предпочтений. На первое место в этом списке следует записать того человека, с кем ему или ей более всего хотелось бы вступить в брак, на второе место — того, с кем хотелось бы создать семью, если с первым из списка это никак невозможно, и т.д. Все списки должны включать всех n кандидатов.

А когда списки будут составлены — поделить всех на пары. При этом каждый человек в паре должен быть уверен, что все, кто нравился ему больше, чем тот, кто оказался с ним рядом, оказались в паре с теми, кто нравился им больше него. Будем называть набор пар раскладом и (в этом случае) будем говорить, что расклад является устойчивым.

Поясним это более формально. Рассмотрим две пары (m1, f1) и (m2, f2). Предположим, что m2 желал бы видеть своей парой f1 более, чем f2 (т.е. в списке m2 номер f1 меньше, чем f2). Однако f1 полагает, что m1 лучший выбор, нежели m2 (т.е. в списке f1 номер m1 меньше, чем m2).

Если бы это было не так, то расклад устойчивым считать было бы уже нельзя: ведь m2 и f1 могли бы стремиться друг к другу.

Однако Принцесса засомневалась, что при таком раскладе все будут счастливы: ведь может случиться так, что в одной паре окажутся поставившие друг друга в самый конец своих списков.

Конечно, Дракон уже думал об этом раньше и пришёл к выводу, что для каждого возможного расклада можно ввести характеристику «недовольство». Мерой «недовольства» конкретного человека он считает номер его партнёра в паре в его списке. А мерой «недовольства» расклада — максимальный среди всех таких номеров.

Ваша задача — по заданным спискам предпочтений найти (устойчивый) расклад с минимально возможным «недовольством».

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 200) — количество участников пар с каждой стороны.

В каждой из следующих n строк содержатся предпочтения очередного принца (или рыцаря) — некоторая перестановка чисел от 1 до n.

В каждой из следующих n строк содержатся предпочтения очередной принцессы — также некоторая перестановка чисел от 1 до n.

Считайте, что принцы и рыцари, равно как и принцессы, занумерованы в порядке их упоминания во входных данных.

Выходные данные

В первой строке выведите единственное целое число — минимально возможную меру «недовольства» в раскладе.

Во второй строке выведите собственно расклад — n целых чисел pj, где pj —номер принцессы, которая должны оказаться в паре с принцем (рыцарем) #j.

Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
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
Примечание

Поясним пример. Покажем, что полученный расклад устойчив.

Рассмотрим пару (1, 1). Для первого партнёра его текущий выбор имеет #3 в его списке, и он был бы рад встречаться с 3 или (если уж 3 не пожелает) с 4. Для второго партнёра его текущий выбор имеет #2 в его списке, и он был бы рад встречаться с 3.

В паре (2, 3) оба партнёра являются друг для друга наилучшим выбором (имеют номер #1 в списке другого партнёра) и не желают встречаться с кем-либо ещё.

В паре (3, 4) первый партнёр уверен в своём выборе (это #1 в его списке), а вот второй партнёр был бы готов сменить 3 на 4 или (если 4 не захочет) 2.

В паре (4, 2) ситуация, похожая на ситуацию в предыдущей паре. Первый партнёр не хотел бы ничего менять, а второй — готов уйти к 2 или (при несогласии 2) к 3.

Посмотрим, каковы перспективы описанных выше желаний.

Первый партнёр из (1, 1) может обратиться к 3, но 3 состоит в паре (2, 3) и ничего менять не хочет. Если же он обратится к 4, то 4 (состоящий в паре (3, 4), хотя и готов сменить своего текущего партнёра, не имеет при этом в виду 1. Второй партнёр может обратиться к 3 (опять же из пары (3, 4)), но не будет иметь успеха: с точки зрения 3, у него сейчас лучший выбор.

Второй партнёр из пары (3, 4) хотел бы сменить текущего партнёра, но желанные для него 4 и 2 сделали лучший выбор.

Второй партнёр из пары (4, 2) также будет отвергнут желанными для него 2 и 3 (из пар (2, 3) и (3, 4) соответственно).

Максимально недовольными в сложившихся парах являются первый партнёр из пары (1, 1) и вторые партнёры из пар (3, 4) и (4, 2): их недовольство составляет 3 (номер их текущего партнёра в списке их предпочтений).

Убедиться в том, что меньшего недовольства для расклада добиться не получится, можно, к примеру, перебрав все остальные возможные расклады: они либо окажутся нестабильны, либо максимальное недовольство кого-либо из партнёров будет не меньше 3.