Ексклюзивний доступ 2
Вивчивши протоколи взаємного виключення на минулорічному конкурсі, ви тепер стикаєтеся з більш складною проблемою. У вас є велика корпоративна система з кількома одночасно працюючими процесами. Система має кілька ресурсів — бази даних, черги повідомлень тощо. Кожен процес працює з двома ресурсами одночасно. Наприклад, один процес може копіювати завдання з певної бази даних у чергу повідомлень, інший процес може брати завдання з черги повідомлень, виконувати його, а потім поміщати результат в іншу чергу повідомлень тощо.
Усі ресурси захищені від одночасного доступу протоколами взаємного виключення, також відомими як блокування. Наприклад, щоб отримати доступ до певної бази даних, процес отримує блокування для цієї бази даних, потім виконує свою роботу, а потім звільняє блокування. Жодні два процеси не можуть утримувати одне й те ж блокування одночасно (це властивість взаємного виключення). Таким чином, процес, який намагається отримати блокування, чекає, якщо це блокування зайняте іншим процесом.
Основний цикл процесу, який працює з ресурсами P та Q, виглядає так:
"' loop forever
DoSomeNonCriticalWork()
P.lock()
Q.lock()
WorkWithResourcesPandQ()
Q.unlock()
P.unlock()
end loop "'
Порядок, у якому блокування для ресурсів P та Q беруться, є важливим. Розгляньте випадок, коли процес c отримав блокування P за допомогою P.lock() і чекає на блокування Q у Q.lock(). Це означає, що блокування Q зайняте іншим процесом d. Якщо процес d працює (не чекає), то ми кажемо, що існує ланцюг очікування довжиною 1. Якщо d отримав блокування Q і чекає на інше блокування R, яке зайняте працюючим процесом e, то ми кажемо, що існує ланцюг очікування довжиною 2 тощо. Якщо будь-який процес у цьому ланцюзі очікування чекає на блокування P, яке вже зайняте процесом c, то ми кажемо, що ланцюг очікування має нескінченну довжину і система зависає.
Для цієї задачі нас цікавлять лише чергуючі ланцюги очікування, де процеси утримують свої перші блокування і чекають на другі. Формально:
Чергуючий ланцюг очікування довжиною n (n >= 0) є чергуючою послідовністю ресурсів R_i (0 <= i <= n+1) та різних процесів c_i (0 <= i <= n): R_0 c_0 R_1 c_1 … R_n c_n R_n_{+1}, де процес c_i отримує блокування для ресурсів R_i та R_i_{+1 у цьому порядку. Чергуючий ланцюг очікування є зависанням, коли }R_0 = R_n_{+1}.
Вам надано набір ресурсів, з якими працює кожен процес. Ваше завдання — визначити порядок, у якому кожен процес має отримувати блокування своїх ресурсів, щоб система ніколи не зависала, а максимальна довжина будь-якого можливого чергуючого ланцюга очікування була мінімізована.
Вхідні дані
Перша строка вхідного файлу містить одне ціле число n (1 <= n <= 100) — кількість процесів. Наступні n рядків описують ресурси, які потрібні кожному процесу. Кожен ресурс позначається великою англійською літерою від L до Z, тому є не більше 15 ресурсів. Кожен рядок, що описує процес, містить два різні ресурси, розділені пробілом.
Вихідні дані
На першій строкі вихідного файлу напишіть одне ціле число m — мінімально можливу довжину максимального чергуючого ланцюга очікування.
Потім напишіть n рядків — по одному рядку на процес. У кожному рядку напишіть два ресурси в порядку, в якому вони повинні бути взяті відповідним процесом, щоб забезпечити цю мінімальну довжину максимального чергуючого ланцюга очікування. Розділіть ресурси в рядку пробілом. Порядок процесів у виході повинен відповідати їх порядку у вхідних даних.