Кот Бенедикт уже несколько дней недоумевает: вместо фильмов про животных хозяева целыми днями смотрят странные (с точки зрения кота) игры людей. Эти люди бегают по большому полю за одним-единственным мячом, пытаясь отобрать его друг у друга.
Бенедикт уже не раз слышал, что есть $$$4$$$ команды, которые для определённости будем называть $$$A$$$, $$$B$$$, $$$C$$$ и $$$D$$$. Каждая из этих команд должна сыграть с каждой по одному разу. Таким образом, всего должно быть сыграно $$$6$$$ матчей. Часть матчей уже состоялась, а часть — скоро состоится.
Результатом матча может быть ничья, за которую каждой из команд начисляют по одному очку, или выигрыш одной из команд и, соответственно, проигрыш другой. Выигравшей команде начисляют три очка, проигравшей — ноль очков.
Очки суммируются, и команда, набравшая максимальное количество очков, занимает первое место. Если максимальное количество очков набирает несколько команд, то все такие команды считаются занявшими первое место.
Бенедикт знает, что хозяева переживают за команду $$$A$$$ и очень хотят, чтобы она заняла первое место. Ваша задача — зная результаты уже состоявшихся матчей, определить, может ли команда $$$A$$$ занять первое место, и если да, то с какими результатами должны завершиться ещё не состоявшиеся матчи.
В первой строке содержится целое число $$$n$$$ $$$(4 \le n \le 5)$$$ —количество уже состоявшихся матчей.
Далее следует $$$n$$$ строк, в каждой из которых содержится по три символа $$$t_1$$$, $$$r$$$, $$$t_2$$$ $$$(t_1, t_2 \in \{A, \, B, \, C, \, D \}, \, t_1 \not= t_2, \, r \in \{ W, \, R \} )$$$, $$$t_1$$$ и $$$t_2$$$ – наименования команд, а $$$r$$$ — результат их игры: $$$W$$$ означает, что команда $$$t_1$$$ победила команду $$$t_2$$$, а $$$R$$$ — что команды $$$t_1$$$ и $$$t_2$$$ сыграли вничью (посмотрите пример ниже для лучшего понимания формата).
Гарантируется, что все описанные матчи попарно различны.
В первой строке выведите $$$YES$$$, если возможны такие результаты оставшихся матчей, при которых команда $$$A$$$ может занять первое место, и $$$NO$$$ — если ни при каких результатах оставшихся матчей команда $$$A$$$ не займёт первое место.
Если в первой строке выведено $$$YES$$$, далее следуют $$$6-n$$$ строк, в которых записаны результаты оставшихся матчей, при которых команда $$$A$$$ займёт первое место, в таком же формате, как во входных данных.
Если существует несколько вариантов правильного ответа, выведите любой из них.
Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$n = 5$$$, в оставшемся матче | нет | полная |
| команда $$$A$$$ участвует | ||||
| 2 | 2 (до 20) | $$$n = 5$$$, в оставшемся матче | 1 | полная |
| команда $$$A$$$ не участвует | ||||
| 3 | 2 (до 10) | $$$n = 4$$$, в обоих оставшихся матчах | 1 | полная |
| команда $$$A$$$ участвует | ||||
| 4 | 2 (до 30) | $$$n = 4$$$, в одном из оставшихся матчей | 1, 2, 3 | полная |
| команда $$$A$$$ участвует, в другом — нет | ||||
| 5 | 2 (до 30) | $$$n = 4$$$, в обоих оставшихся матчах | 1, 2, 3, 4 | полная |
| команда $$$A$$$ не участвует |
5 A W B C W A B W C C R D D R B
YES A R D
4 A R B C W B D W A C R D
YES A W C B W D
4 A R B B W C D W A C W D
NO
Поясним приведённые примеры.
В первом примере единственная ещё не состоявшаяся игра — это игра между командами $$$A$$$ и $$$D$$$.
Подсчитаем количество очков, которые набрали команды.
Команда $$$A$$$ выиграла у $$$B$$$ ($$$3$$$ очка) и проиграла $$$C$$$ ($$$0$$$ очков), и на настоящий момент имеет $$$3$$$ очка.
Команда $$$B$$$ проиграла команде $$$A$$$ ($$$0$$$ очков), выиграла у команды $$$C$$$ ($$$3$$$ очка), а также сыграла вничью с командой $$$D$$$ ($$$1$$$ очко). Итого у команды $$$B$$$ $$$4$$$ очка.
Команда $$$C$$$ выиграла у команды $$$A$$$ ($$$3$$$ очка), проиграла команде $$$B$$$ ($$$0$$$ очков), сыграла вничью с командой $$$D$$$ ($$$1$$$ очко), так что суммарно набрала $$$4$$$ очка.
Наконец, команда $$$D$$$ дважды сыграла вничью: с командой $$$B$$$ и с командой $$$C$$$, поэтому имеет $$$2$$$ очка.
Как понятно, команде $$$A$$$ достаточно не проиграть команде $$$D$$$. В случае ничьей она наберёт $$$4$$$ очка и займёт одно из первых мест (что допустимо по условиям задачи), в случае победы у неё будет $$$6$$$ очков, что сделает её абсолютным победителем.
Таким образом, корректными будут следующие ответы:
$$$$$$ A \quad R \quad D$$$$$$ $$$$$$ D \quad R \quad A$$$$$$ $$$$$$ A \quad W \quad D$$$$$$
В качестве ответа в этом примере выведен второй из перечисленых.
Во втором примере сыграно четыре игры. Как несложно определить, что между собой ещё не играли пара $$$A$$$ и $$$C$$$ и пара $$$B$$$ и $$$D$$$.
После этих четырёх игр команды $$$A$$$ и $$$B$$$ имеют по одному очку, а команды $$$C$$$ и $$$D$$$ по четыре очка. За одну игру команда не может набрать более трёх очков, поэтому если хотя бы одна из команд $$$C$$$ или $$$D$$$ не проиграет, она займёт первое место. Проигрыш этих команд обеспечивается выигрышем команд $$$A$$$ и $$$B$$$: в этом случае именно они поделят первое место в группе.
В третьем примере также сыграно четыре игры, и между собой ещё не играли пара $$$A$$$ и $$$C$$$ и пара $$$B$$$ и $$$D$$$ (как и во втором примере).
Однако ситуация с набранными очками здесь другая. Команда $$$A$$$ набрала лишь одно очко, в то время как команда $$$B$$$ имеет четыре очка, а команды $$$C$$$ и $$$D$$$ — по три очка. Даже если команда $$$A$$$ выиграет свою игру и наберёт четыре очка, она не сможет занять первое место. В игре между командами $$$B$$$ и $$$C$$$ любой исход плох для $$$A$$$. Действительно, при победе $$$B$$$ набирает $$$7$$$ очков и становится единоличным лидером. В случае ничьей у команды $$$B$$$ будет $$$5$$$ очков, и обойти её может команда $$$D$$$, выиграв у $$$A$$$, но никак не команда $$$A$$$. Наконец, если выиграет команда $$$C$$$, то она наберёт $$$6$$$ очков и займёт первое место.
Таким образом, команда $$$A$$$ не сможет занять первое место ни при каких результатах оставшихся игр.
