Дороги

В Берляндии есть n городов. При проектировании транспортной системы страны было решено между каждой парой городов u и v (u < v) построить либо автотрассу, либо железную дорогу (то есть будет построен ровно один из этих двух типов дорог). Оба типа дорог являются односторонними.

Теперь власти рассматривают несколько проектов построения дорог. Они считают проект оптимальным, если не существует двух таких городов, что между ними можно добраться как только по автотрассам, так и только по железной дороге (возможно, проезжая через другие города).

Определите для заданного проекта, является ли он оптимальным.

Входные данные

В первой строке входного файла INPUT.TXT записано натуральное число n (1 ≤ n ≤ 3000) - количество городов в Берляндии.

Далее следует (n-1) строк, описывающих проект построения дорог. В i-той из них вводится (n-i) символов «R» и «A», обозначающих тип дороги, ведущей из города с номером i в города с номерами (i+1), (i+2), … , n, соответственно. Символ «R» означает железную дорогу, символ «A» – автотрассу.

Выходные данные

Если проект является оптимальным, то в единственную строку выходного файла OUTPUT.TXT нужно вывести «Yes».

Если проект не является оптимальным, то в первой строке выведите «No», а во второй – два натуральных числа u и v – номера любых двух городов, между которыми можно добраться как по железной дороге, так и по автотрассам. Если вариантов ответа несколько, выведите любой. Города можно выводить в любом порядке.

Примеры

Система оценки

Решения, работающие для n ≤ 300, будут оцениваться в 50 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]