Алексей, Борис и Василий скоро примут участие в командном шахматном соревновании. Так как они все в одной команде, они решали вместе потренироваться перед турниром. Однако, это оказалось сделать не так просто, ведь шахматы — игра для двух человек.
Тогда они решили играть по следующим правилам:
- Алексей и Борис играют первую игру, Василий наблюдает;
- Когда игра заканчивается, проигравший становится наблюдателем, а предыдущий наблюдатель садится играть против победителя.
Алексей, Борис и Василий играют таким образом, что ничьих не случается.
Сегодня они сыграли n игр, после каждой запоминали победителя. Они решили записать историю игр, описывающую, кто победил в каждой из них. Но теперь они сомневаются, что записанная информация корректна, и хотят узнать, могла ли получиться такая история (то есть, нет таких игр, в которых побеждает игрок, следящий за матчем). Помогите им проверить это!
Примечание
В первом примере возможна следующая ситуация:
- Алексей выигрывает, следующую партию вместо Бориса играет Василий;
- Алексей выигрывает, Борис заменяет Василия;
- Борис выигрывает.
Ситуация во втором примере невозможна, так как Борис проигрывает первую партию и поэтому не может участвовать во второй.