말 전하기 게임

친구 N명이 말 전하기 게임을 한다. 1번이 대장이고, 대장이 나머지 친구 각각에게 cat 또는 hat 중 한 단어를 말하면서 게임이 시작된다. N명 가운데 m명은 발음이 나빠서, 이 친구가 hat이라고 말해도 듣는 쪽은 cat으로 알아듣는다. 문제를 간단히 하려고, 이런 친구는 누구에게 무슨 말을 들었든 다른 친구에게는 항상 cat이라고 말한다고 하자. 대장도 그중 한 명일 수 있고, 그러면 친구마다 다른 단어를 말한다.

친구들은 하나의 단어로 합의하려고 WBM(m) 알고리즘을 돌린다.

WBM(m) 알고리즘, m > 0

1. 대장이 나머지 친구 모두에게 자기 단어를 보낸다.
2. 친구 $i$가 대장에게 받은 단어를 $v_i$라고 하자. 친구 $i$는 이번 호출에 참여한 친구 가운데 자신과 이번 대장을 뺀 나머지를 상대로 WBM(m-1)의 대장이 되어 $v_i$를 보낸다. 친구 $i$에서 출발한 메시지는 다시 $i$에게 돌아오지 않는다.
3. 각 $i$와 $j \ne i$에 대해, 친구 $i$가 2단계에서 친구 $j$에게 받은 단어를 $v_j$라고 하자. 친구 $i$는 $v_1, v_2, \dots, v_{N-1}$ 가운데 더 많이 나온 단어를 자기 단어로 삼는다. 두 단어가 같은 횟수로 나오면 cat을 고른다.

WBM(0) 알고리즘

1. 대장이 나머지 친구 모두에게 자기 단어를 보낸다.
2. 각 친구는 대장에게 받은 단어를 그대로 쓴다.

게임은 대장이 WBM(m)을 돌리면서 시작한다. 친구는 말을 전할 때마다 자기 번호를 메시지에 붙이므로, 받는 쪽은 그 메시지가 어떤 경로로 왔는지 안다. 대장이 처음에 보내는 메시지에는 경로가 붙지 않는다.

첫 번째 그림은 $N = 4$이고 대장이 2번에게 cat을, 3번과 4번에게 hat을 보내는 경우다. 2번은 1번에게 cat, 3번에게 hat, 4번에게 hat을 받아 hat을 고른다. 3번은 1번에게 hat, 2번에게 cat, 4번에게 hat을 받아 hat을 고른다. 4번은 1번에게 hat, 2번에게 cat, 3번에게 hat을 받아 hat을 고른다. 대장이 서로 다른 단어를 말했는데도 대장을 뺀 세 친구가 모두 같은 단어에 이른다.

그림 1. 친구 $N = 4$명, 대장 $i = 1$이 잘못 발음한 단어를 보내는 경우.

두 번째 그림도 $N = 4$이지만, 이번에는 $m = 2$명, 곧 2번과 3번이 발음을 틀리고 대장은 모두에게 hat이라고 말한다. 오가는 메시지가 더 많아진다. 2번이 3번에게 cat을 보내고 3번이 이를 4번에게 넘긴다. 그림에는 2,3:cat으로 적혀 있다. 2번은 4번에게도 cat을 바로 보내고, 그림에는 2:cat으로 적혀 있다. 그래서 4번은 2번 몫으로 cat을 두 번 받고 2번이 cat이라고 말했다고 판단한다. 마찬가지로 4번은 3번에게 cat을 바로 받고 3,2:cat 경로로 cat을 한 번 더 받아, 3번도 cat이라고 말했다고 판단한다. 대장은 4번에게 hat이라고 말했다. 더 많이 나온 단어가 cat이므로 4번은 cat을 고른다.

그림 2. 친구 $N = 4$명, 2번과 3번이 잘못 발음한 단어를 보내는 경우.

대장을 뺀, 발음이 정확한 친구가 고른 단어를 모두 구하여라. 대장의 발음이 정확하면 그런 친구는 $N - m - 1$명이고, 그렇지 않으면 $N - m$명이다.

첫째 줄에 N과 m이 주어진다. ($2 < N < 101$, $0 < m < 8$) 둘째 줄에 단어를 바꿔 말하는 친구의 번호 m개가 서로 다르게 주어진다. 대장의 번호는 항상 1이다. 이어지는 $N - 1$개 줄에는 대장이 $2, 3, \dots, N$번 친구에게 차례로 보내는 단어 cat 또는 hat이 한 줄에 하나씩 주어진다. 대장의 발음이 정확하면 이 $N - 1$개 단어는 모두 같다.

대장을 뺀, 발음이 정확한 친구가 고른 단어를 친구 번호가 커지는 순서로 한 줄에 하나씩 출력한다. 대장의 발음이 정확하면 $N - m - 1$줄, 그렇지 않으면 $N - m$줄이 나온다.