Вы создали очередную платформу для проведения онлайн соревнований по программированию. После первого контеста вы изучили решения участников и заметили, что некоторые списывают друг у друга. После этого вам захотелось написать программу, чтобы быстрее обнаруживать списывания и блокировать нечестных участников.
Пусть есть две строки, описывающие решения. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После этого для рассматриваемого символа $$$x$$$ определим другой символ $$$p(x) \neq x$$$ и заменим некоторые вхождения $$$x$$$ в первое решение на $$$p(x)$$$. Если в ходе такого процесса из первого решения возможно получить второе, то скажем, что второе решение списано с первого.
Иными словами, участник копирует чужое решение и, чтобы списывание не было таким очевидным, один раз рассматривает некоторые различные символы $$$x$$$, которые хотя бы раз встречаются в первом решении. Для каждого такого символа $$$x$$$ он выбирает, на какой другой символ $$$p(x)$$$ он будет заменять его вхождения, после чего проходит по строке и заменяет в ней $$$x$$$ на $$$p(x)$$$, но на некоторых позициях забывает это сделать (или там замена невозможна).
Значения $$$p(x)$$$ участником выбираются независимо для разных $$$x$$$, поэтому они могут и совпасть.
Напишите программу, которая позволит обнаружить списывания такого рода.
Кроме платформы вы создали язык программирования S++ и, чтобы его популяризировать, вы решили разрешить сдавать задачи в своей системе только на нем. Одной из особенностью языка является то, что любая программа записывается в одну строку и может состоять только из строчных и заглавных букв английского алфавита (a-z, A-Z), цифр (0-9), скобок ('(', ')', '{', '}' '[', ']'), знаков сравнения ('<', '>', '=') и символов '+', '-', '*', '/', ';'.
В первой строке вам дано число $$$n$$$ $$$(1 \leqslant n \leqslant 200\,000)$$$, равное длине каждой из программ.
Во второй строке вам дана программа первого участника на языке S++.
В третьей строке вам дана программа второго участника на языке S++.
Если вторая программа списана с первой, выведите «YES» (без кавычек), на следующей строке выведите $$$m$$$ – количество различных символов в первой программе, которые хотя бы раз заменялись. Обозначим эти символы за $$$c_1,\ c_2,\ \ldots, \ c_m$$$. После этого выведите $$$m$$$ строк. На $$$i$$$-й строке необходимо вывести символы $$$c_i$$$ и $$$p(c_i)$$$ через пробел. Если вторая программа не списана с первой, то выведите «NO» (без кавычек).
16 for(i=0;i<n;++i) for(j=0;j<m;++j)
YES 2 i j n m
14 a=1;b=-1;c=a-b e=1;f=+1;g=e+f
YES 4 - + a e b f c g
5 a=a+a a=c+d
NO
4 aaab abbb
YES 1 a b
6 aaabcc abbbaa
YES 2 a b c a
3 abc aaa
YES 2 b a c a
В первом примере списывающий заменил все вхождения 'i' на 'j' и вхождения 'n' на 'm'.
Во втором примере участник заменял 'a' на 'e', 'b' на 'f', 'с' на g' и '-' на '+'.
В третьем примере невозможно осуществить процесс замен так, чтобы из первой строки получилась вторая.
В четвертом примере участник списал, заменив некоторые вхождения 'a' на 'b'.
В пятом примере участник списал, заменив некоторые вхождения 'a' на 'b' и все вхождения 'c' на 'a'.
В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие, когда обе программы состоят только из символов 'a' и 'b', наберут не менее 20 баллов.
Решения, корректно работающие, когда обе программы состоят только из символов 'a', 'b', 'c', наберут не менее 40 баллов.
Решения, корректно работающие при $$$n \leqslant 1\,000$$$ наберут не менее 60 баллов.
Решения, корректно работающие только для случая, когда обнаружить списывание не удалось, оцениваются в 0 баллов.