20528번 - 끝말잇기

욱제는 준원이랑 끝말잇기를 하고 있다. 준원이가 시작하자마자 '스트론튬'을 외쳐서 욱제는 피가 거꾸로 솟았다~ 솟으면 백두산~ 백두산은 높아~ 높으면 비행기~ 비행기는 빨라~ 빠르면 기차~ 기차에 타고 내릴 때에는 코로나 바이러스 감염증 예방을 위하여 마스크를 착용하여 주시길 당부 드립니다.

준원이와의 끝말잇기 대결에서 패배한 욱제는 새로운 게임을 제안했다. 바로 팰린드롬 문자열만 사용할 수 있는 팰린드롬 끝말잇기이다! 욱제와 준원이는 총 $N$개의 팰린드롬 문자열 $S_1, \cdots, S_N$을 알고 있다. 이 둘이 알고 있는 팰린드롬 문자열을 남김 없이 모두 사용했을 때, 끝말잇기를 할 수 있는지 알아보자. 문자열을 사용하는 순서는 상관 없다.

"리효리", "찰진 의사의 진찰", "탄도유도탄"과 같이 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 팰린드롬 문자열이라고 부른다. 다시 말해, 길이 $M$짜리 문자열 $T$에 대해, $T[i] = T[M-i+1]$ ($1 \le i \le M$)이면 $T$는 팰린드롬 문자열이다.

$N$개의 팰린드롬 문자열 $P_1, \cdots, P_N$에 대해, $P_i$의 마지막 문자와 $P_{i+1}$의 첫 문자가 같으면 끝말잇기를 할 수 있다고 정의한다. ($1 \le i < N$)

첫째 줄에 문자열의 개수 $N$이 주어진다.

둘째 줄에 $N$개의 팰린드롬 문자열 $S_1, \cdots, S_N$이 하나의 공백을 사이에 두고 주어진다.

주어진 팰린드롬 문자열을 모두 사용했을 때 끝말잇기를 할 수 있으면 1, 그렇지 않다면 0을 출력한다.

• $1 \le N \le 100$
• $1 \le \left|S_i \right| \le 100$, $\left| S_i \right|$는 문자열 $S_i$의 길이를 의미한다.
• $S_i$는 알파벳 소문자로만 구성된 팰린드롬 문자열이다.