시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)63914012023.346%

문제

블록체인 컨설팅 회사 SCVSoft에서는 두 대의 건설 로봇(SCV)이 일하고 있다. 두 로봇에게는 “A”와 “B”라는 멋진 이름이 붙어 있다.

어느 날, 심심해진 두 로봇은 블록체인 만들기 놀이를 하기로 했다. 놀이의 규칙은 다음과 같다.

  1. $2N$개의 나무 블록에 $1$번부터 $2N$번까지 번호를 매기고, 각자 $N$개씩 나눠 갖는다.
  2. 로봇 A부터 시작해 번갈아가며 다음의 두 동작 중 하나를 한다.
    • 블록: 가지고 있는 블록 중 하나를 바닥에 놓는다.
    • 체인: 가지고 있는 블록 중 하나를 바로 전에 상대방이 놓은 블록 위에 올려놓는다. 이때, 새로 놓는 블록의 번호는 상대방이 놓은 블록의 번호보다 커야 한다.

    처음 놀이를 시작할 때는 상대방이 놓은 블록이 없으므로, A는 반드시 블록 동작을 한다.

  3. 각자 $N$번의 동작을 해서 가진 블록이 다 떨어지면 놀이가 끝난다.

여기서 블록 동작은 새로운 블록체인의 시작을 본뜬 중요한 동작이기 때문에, 로봇들은 블록 동작을 할 때마다 어떤 블록을 놓았는지 작은 데이터베이스에 기록으로 남긴다. 데이터베이스는 기록들을 요청이 들어온 순서에 따라 안전하게 저장한다. 그러나 로봇과 데이터베이스 사이의 통신은 약간 불안정해서, 기록을 남기다 보면 기록 저장 요청을 보낸 로봇을 혼동하거나 요청을 누락하는 등의 오류가 발생하기도 한다.

로봇들이 놀이를 한 차례 진행한 뒤 데이터베이스에 저장된 기록이 주어진다. 이때 이 기록이 통신에 오류가 없었다고 가정할 때 놀이에서 실제로 나올 수 있는 기록인지 판별하고, 만약 그렇다면 기록에 체인 동작을 적절히 추가해 놀이에서 있었던 모든 동작이 담긴 기록으로 만들어 보자.

입력

첫 번째 줄에 두 개의 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $M$은 데이터베이스에 저장된 블록 동작 기록의 개수이다. $(1\le N\le 100\, 000$; $1\le M\le 2N)$

이후 $M$줄에 걸쳐 블록 동작 기록이 한 줄에 하나씩 주어진다. 기록은 <robot> BLOCK <number> 꼴으로, <robot>에는 동작을 한 로봇의 이름, <number>에는 로봇이 놓은 블록의 번호가 들어간다.

주어지는 기록의 순서는 데이터베이스에 저장된 순서를 따른다. 기록의 첫 번째 동작은 반드시 로봇 A의 동작이며, 기록에 등장하는 블록들의 번호는 모두 $1$ 이상 $2N$ 이하의 정수이고 중복되지 않음이 보장된다.

출력

첫 줄에 주어진 블록 동작 기록이 놀이에서 나올 수 있는 기록이라면 YES, 그렇지 않다면 NO를 출력한다.

YES를 출력했을 경우, 이후 $2N$줄에 걸쳐 주어진 기록에 체인 동작을 추가한 전체 동작 기록을 입력과 같은 형식으로 출력한다. 체인 동작은 <robot> CHAIN <number> 꼴으로 나타낸다. 주어진 기록으로부터 만들 수 있는 전체 동작 기록이 여러 가지일 경우 그중 아무것이나 출력한다.

예제 입력 1

6 5
A BLOCK 8
A BLOCK 1
B BLOCK 3
B BLOCK 6
A BLOCK 4

예제 출력 1

YES
A BLOCK 8
B CHAIN 9
A BLOCK 1
B CHAIN 2
A CHAIN 10
B BLOCK 3
A CHAIN 5
B BLOCK 6
A CHAIN 7
B CHAIN 11
A BLOCK 4
B CHAIN 12

예제 입력 2

4 3
A BLOCK 4
B BLOCK 2
A BLOCK 7

예제 출력 2

NO