아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

끝말잇기 하실 분!!

시간 제한1초메모리 제한1024 MB

요약
M개의 단어가 주어질 때, 먼저 시작하는 곰곰이 특정 단어로 게임을 시작해 이길 수 있는 단어의 수와 목록을 구한다.
난이도

보통10점 중 7점

유형
그래프, 게임 이론, DFS
정답자
아직 제출이 없습니다

문제

총총: 밥? 곰곰: 밥!

곰곰과 총총은 끝말잇기를 하고 있다. 끝말잇기는 두 명이서 번갈아 가며 상대방이 말한 단어의 끝 글자로 시작하는 단어를 말하는 게임이다.

끝말잇기에 사용 가능한 MM개의 단어 목록이 주어지고, 곰곰과 총총은 여기에 있는 단어만 사용해야 한다. 한 단어는 여러 번 사용할 수 있다.

자신의 차례가 왔을 때 말할 수 있는 단어가 없다면 패배하게 되고, 게임이 끝나지 않는다면 무승부로 간주한다.

곰곰과 총총은 자신이 이기기 위해 최선을 다하고, 이길 수 있는 방법이 없다면 무승부를 위해 최선을 다한다고 하자.

게임은 곰곰이 먼저 시작한다. 곰곰은 MM개의 단어 중, 자신이 처음에 골라서 이길 수 있는 단어가 몇 가지나 되는지 알고 싶다.

단어의 수가 많아 힘들어하고 있는 곰곰을 위해 당신이 답을 구해 알려주도록 하자!

곰곰: 고맙습니다

입력

첫번째 줄에는 정수 MM이 주어진다. (1≤M≤100,000)(1 \le M \le 100\\,000)

두번째 줄부터 MM개의 줄에 걸쳐 지문에서 설명된 단어 목록이 주어진다. 단어의 길이는 11 이상 2020 이하이며, 영문 소문자로만 이루어져 있다.

같은 단어가 여러 번 주어지는 경우는 없다.

출력

첫번째 줄에는, MM개의 단어 중 곰곰이 해당 단어로 게임을 시작했을 때 게임을 이길 수 있는 단어의 개수 KK를 출력한다. (1≤K≤M)(1 \le K \le M)

두번째 줄부터 KK개의 줄에 걸쳐 단어들을 사전 순으로 출력한다.

예제4

  1. 예제 1

    입력
    5
    sheet
    toxic
    cave
    eel
    cog
    
    예상 출력
    3
    cog
    eel
    sheet
    
  2. 예제 2

    입력
    6
    arab
    abat
    tech
    hola
    cola
    spec
    
    예상 출력
    3
    arab
    spec
    tech
    
  3. 예제 3

    입력
    7
    arab
    abat
    tech
    hola
    cola
    spec
    chic
    
    예상 출력
    2
    arab
    tech
    
  4. 예제 4

    입력
    4
    ab
    ba
    ac
    d
    
    예상 출력
    2
    ab
    ac