시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 140 | 23 | 16 | 15.686% |
곰곰과 총총은 끝말잇기를 하고 있다. 끝말잇기는 두 명이서 번갈아 가며 상대방이 말한 단어의 끝 글자로 시작하는 단어를 말하는 게임이다.
끝말잇기에 사용 가능한 $M$개의 단어 목록이 주어지고, 곰곰과 총총은 여기에 있는 단어만 사용해야 한다. 한 단어는 여러 번 사용할 수 있다.
자신의 차례가 왔을 때 말할 수 있는 단어가 없다면 패배하게 되고, 게임이 끝나지 않는다면 무승부로 간주한다.
곰곰과 총총은 자신이 이기기 위해 최선을 다하고, 이길 수 있는 방법이 없다면 무승부를 위해 최선을 다한다고 하자.
게임은 곰곰이 먼저 시작한다. 곰곰은 $M$개의 단어 중, 자신이 처음에 골라서 이길 수 있는 단어가 몇 가지나 되는지 알고 싶다.
단어의 수가 많아 힘들어하고 있는 곰곰을 위해 당신이 답을 구해 알려주도록 하자!
첫번째 줄에는 정수 $M$이 주어진다. $(1 \le M \le 100\,000)$
두번째 줄부터 $M$개의 줄에 걸쳐 지문에서 설명된 단어 목록이 주어진다. 단어의 길이는 $1$ 이상 $20$ 이하이며, 영문 소문자로만 이루어져 있다.
같은 단어가 여러 번 주어지는 경우는 없다.
첫번째 줄에는, $M$개의 단어 중 곰곰이 해당 단어로 게임을 시작했을 때 게임을 이길 수 있는 단어의 개수 $K$를 출력한다. $(1 \le K \le M)$
두번째 줄부터 $K$개의 줄에 걸쳐 단어들을 사전 순으로 출력한다.
5 sheet toxic cave eel cog
3 cog eel sheet
6 arab abat tech hola cola spec
3 arab spec tech
7 arab abat tech hola cola spec chic
2 arab tech
4 ab ba ac d
2 ab ac