아싸 너!
시간 제한2초메모리 제한512 MB
N명이 둘러앉은 게임에서 준서의 동작이 M번 자리에 놓인 배열을 만들 수 있는지 판별하고, 가능하면 지목 순서를 출력합니다.
문제
준서는 술을 잘 못 마신다. 하지만 준서는 한 소학회의 회장이기 때문에, 새내기 배움터에서의 술 게임을 피할 수 없다. 내가 못 마신다면 남들을 많이 먹이면 되지! 준서는 고민 끝에 아주 어려운 술 게임을 준비해 새내기들을 골탕 먹일 계략을 세웠다.
준서와 새내기 명이 둥글게 둘러앉아 술 게임을 시작한다. 각 자리는 시계방향으로 1번부터 번까지 번호를 가진다. 준서는 항상 1번 자리에 앉는다. 게임을 시작하면서 각자 고유한 모션을 정한다.
술 게임은 다음과 같이 진행된다.
- 준서가 자신의 모션을 취하며 게임을 시작한다.
- 자신을 제외한 명 중 한 명을 손가락으로 지목한다.
- 지목당한 사람의 왼쪽 두 사람이 서로 모션을 바꾼다.
- 지목당한 사람의 오른쪽 두 사람도 서로 모션을 바꾼다.
- 지목당한 사람은 자신이 가졌다고 생각하는 모션을 취한다.
- 지목당한 사람이 가진 모션과 취한 모션이 다르면, 벌칙주를 마시며 게임이 끝난다.
- 같다면, 지목당한 사람이 다른 사람을 지목하며 게임을 계속 진행한다.
- 3번부터 7번까지를 계속해서 반복한다.
신입생들을 골탕 먹일 생각이었던 준서는 당황할 수밖에 없었다. 예상과 달리, 미친 난이도에도 불구하고 게임은 막힘없이 진행되며 끝나질 않는다. 준서의 정신이 아득해질 때쯤, 준서는 어느 순간 모션의 배치가 처음과 완전히 같은 원순열인 것을 눈치챘다!
<그림1> 같은 원순열의 한 예.
같은 원순열이란, <그림1>과 같이 돌렸을 때 같은 경우를 의미한다.
혹시 신입생들이 서로 짜고 틀린 모션을 그냥 넘어간 게 아닐까? 술에 취한 준서는 게임의 진행을 전부 기억하지는 못하지만, 적어도 현재의 모션 배치가 부정 없이 만들어질 수 있는지 확인하고 싶다.
입력
술 게임에 참가하는 사람의 수 과, 현재 준서가 가지고 있는 모션을 가장 처음 가지고 있던 사람이 앉아 있는 자리의 번호 이 차례대로 주어진다.
출력
게임을 무한히 진행하기에는 준서의 체력이 얼마 되지 않으므로, 100만 회의 지목 안에 불가능한 배치라면 "NO"를 출력한다.
가능한 배치라면 첫 번째 줄에 "YES"를 출력한다. 두 번째 줄에는 게임을 시작해서 현재 상태와 같은 모션 배치를 만드는 데 필요한 지목 횟수 을 출력한다. 세 번째 줄에는 지목받은 사람이 앉아 있는 자리의 번호를 공백으로 구분하여 순서대로 출력한다.