Задача №1816. Микросхемы
Авиакомпания собирается оборудовать бортовые компьютеры своих самолётов микросхемами нового типа. К каждой микросхеме, представляющей собой диск, нужно припаять n цветных проводов.
Для удобства было решено, что каждый провод можно припаять к одному из двух разъёмов, предназначенных для этого провода. Разъёмы на микросхеме расположены по кругу. Для повышения безопасности было решено, что никакие два провода одного цвета нельзя припаивать к соседним разъемам.
Дано расположение разъёмов на микросхеме. Требуется найти способ так припаять все провода, чтобы удовлетворить все описанные выше условия.
Первая строка входного файла содержит \(n\) — количество проводов (1 \(\le\) \(n\) \(\le\) 50000). Вторая строка содержит \(n\) целых чисел от 1 до \(10^9\) — цвета проводов. Третья строка содержит 2\(n\) целых чисел и описывает разъёмы. Каждый разъём описывается одним целым числом — номером провода, который можно к нему припаять. Каждое из чисел от 1 до \(n\) встречается ровно два раза. Разъёмы описываются в порядке обхода по часовой стрелке. Заметим, что первый и последний разъёмы также соседние.
Если не существует способа необходимым образом припаять провода, выведите «NO» в первой строке выходного файла.
В противном случае, в первой строке выходного файла выведите «YES». Вторая строка выходного файла должна содержать \(n\) целых чисел. Для каждого провода выведите номер разъёма, к которому его нужно припаять. Разъёмы нумеруются от 1 до 2\(n\) в порядке, в котором они заданы во входном файле. Если решений несколько, можно вывести любое из них.
2 1 1 1 1 2 2
YES 1 3
2 1 1 1 2 1 2
NO
2 1 2 1 2 1 2
YES 1 2