끝말잇기 하실 분!!

• 게임 자체는 간단하게 그래프 형태로 변환이 가능하다. 각 알파벳이 노드가 되고, 각 단어는 첫 글자와 끝 글자를 연결하는 방향엣지가 된다.
• 방향 그래프와 시작 노드가 주어졌을때, 번갈아가면서 엣지를 따라서 다음 노드로 이동하다가, 더 이상 이동이 불가능한 경우 (outdegree가 0인 노드에 도착했을 경우)에 패배하는 형태의 게임은, 게임이론 문제에서 흔히 등장하는 패턴이다.
  • 돌을 옮기거나, 직접 이동하거나 등등 많은 문제들을 본거 같긴 한데, 해당되는 전형적인 문제가 지금 떠오르지는 않는다.. 나중에 생각나면 추가하자..
• 이러한 문제는 DP를 이용하는 기본적인 게임이론 문제의 풀이법과 거의 동일하지만, 기반이 되는 그래프에 사이클이 존재할 수가 있어서 무승부라는 경우가 추가되는 것이 다르다.
• DP를 이용해서 푸는 게임이론 문제 (기반 그래프가 DAG인 경우) 에서의 공식은 다음과 같다. 이것을 기반으로 리프노드부터 위상정렬 순서대로 모든 노드의 상태를 계산할 수 있다.
  • 이동 가능한 노드가 없는 노드 (outdegree가 0인 노드)는 패배 포지션이다
  • 이동 가능한 노드들 중에 패배 포지션이 존재하는 노드는 승리 포지션이다.
  • 이동 가능한 노드들이 모두 승리 포지션인 노드는 패배 포지션이다.
• 사이클이 있는 경우에는 위의 어느 케이스에도 해당되지 않는 노드가 존재하게 된다. 이 노드들을 무승부 포지션으로 만들면 된다. 역시 위상정렬에 기반해서 구현하게 되지만 구현이 좀 더 까다롭다.
  • 시간복잡도는 O(E+V)
• 이 문제에서는 노드의 개수 26, 엣지의 개수는 M이므로, 그래프를 구축하고 각 노드의 상태를 계산하는데까지 O(M)이 걸린다. 답은 단어들 중에서 끝 글자가 패배 포지션인 단어들을 모두 고르면 되고, 전체 시간복잡도는 여전히 O(M)이 된다

"""Solution code for "BOJ 26166. 끝말잇기 하실 분!!".

- Problem link: https://www.acmicpc.net/problem/26166
- Solution link: http://www.teferi.net/ps/problems/boj/26166

Tags: [game theory]
"""

import sys

WIN = 0
LOSE = 1
DRAW = 2


def main():
    M = int(sys.stdin.readline())
    words = [sys.stdin.readline().rstrip() for _ in range(M)]

    rev_graph = [[] for _ in range(26)]
    out_deg = [0] * 26
    for word in words:
        u, v = int(word[0], 36) - 10, int(word[-1], 36) - 10
        rev_graph[v].append(u)
        out_deg[u] += 1

    state_by_node = [DRAW] * 26
    stack = []
    for u, deg in enumerate(out_deg):
        if deg == 0:
            state_by_node[u] = LOSE
            stack.append(u)

    while stack:
        v = stack.pop()
        for u in rev_graph[v]:
            if state_by_node[u] != DRAW:
                continue
            if state_by_node[v] == LOSE:
                state_by_node[u] = WIN
                stack.append(u)
                continue
            out_deg[u] -= 1
            if out_deg[u] == 0:
                state_by_node[u] = LOSE
                stack.append(u)

    answer = sorted(
        x for x in words if state_by_node[int(x[-1], 36) - 10] == LOSE
    )
    print(len(answer))
    print('\n'.join(answer))


if __name__ == '__main__':
    main()