Задача . B. Azamon Web Services

Для привлечения клиентов на свой сайт Azamon ваш друг Jeff Zebos запустил новую онлайн-кампанию. Однако он не смог привлечь так много посетителей, как планировал. Вам кажется, что самая большая проблема заключается в том, что его сайт не получает высокие места в выдаче поисковых систем. Только если он изменит названия продуктов на такие, которые будут лучше чем у конкурентов, он сможет оказаться на первой строчке в поиске и станет миллионером!

После некоторого исследования, вы заметили, что в поиске результаты отсортированы лексикографически. Если ваш друг сможет переименовать свои продукты на лексикографически меньшие строки, чем у конкурентов, он будет первым в поиске!

Чтобы сделать стратегию менее очевидной для конкурентов, вы решили поменять местами не больше одной пары символов в названиях продуктов.

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

Вам дана строка \(s\), являющаяся названием продукта компании Azamon и строка \(c\), являющаяся названием продукта компании конкурента. Найдите некоторый способ поменять не больше одной пары символов в строке \(s\) (это означает выбрать два различных индекса \(i\) и \(j\) и поменять местами символы \(s_i\) и \(s_j\) в строке), так чтобы новое имя стало лексикографически меньше, чем \(c\). Если это невозможно, определите это.

Примечание: Строка \(a\) лексикографически меньше чем строка \(b\), тогда и только тогда, когда одно из следующих двух условий выполнено:

• \(a\) это собственный префикс строки \(b\), то есть, \(a\) это префикс строки \(b\) и \(a \neq b\);
• Существует целое \(1 \le i \le \min{(|a|, |b|)}\), такое что \(a_i < b_i\) и \(a_j = b_j\) для всех \(1 \le j < i\).