У вас были \(n\) положительных целых чисел \(a_1, a_2, \dots, a_n\), записанных по кругу. Для каждой пары соседних элементов (\(a_1\) и \(a_2\), \(a_2\) и \(a_3\), ..., \(a_{n - 1}\) и \(a_n\), и \(a_n\) и \(a_1\)) вы выписали следующее: равны ли элементы в паре или нет.
К сожалению, вы потеряли бумажку с записанным массивом \(a\). Более того, вы боитесь, что и информация о равенстве соседних элементов могла быть повреждена. А потому вас интересует: существует ли массив \(a\), который согласовывается с вашей информацией о равенстве (или неравенстве) соседних элементов?
Выходные данные
Для каждого набора входных данных, выведите YES, если возможно подобрать массив \(a\), который согласуется с вашей информацией из строки \(s\). Иначе, выведите NO.
Можно доказать, что если существует какой-то подходящий массив \(a\), то существует также массив \(a\) из положительных целых чисел меньше или равных \(10^9\).
Примечание
В первом наборе входных данных, вы можете выбрать, например, \(a_1 = a_2 = a_3 = 5\).
Во втором наборе, не существует подходящего массива \(a\), так как, согласно \(s_1\), \(a_1\) равно \(a_2\), но, согласно \(s_2\), \(a_2\) не равно \(a_1\).
В третьем наборе, вы можете, например, выбрать массив \(a = [20, 20, 4, 50, 50, 50, 20]\).
Во четвертом наборе, вы можете, например, выбрать массив \(a = [1, 3, 3, 7]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
EEE
EN
ENNEENE
NENN
|
YES
NO
YES
YES
|