시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1536 MB22331547138070.301%

문제

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

준원이와의 끝말잇기 대결에서 패배한 욱제는 새로운 게임을 제안했다. 바로 팰린드롬 문자열만 사용할 수 있는 팰린드롬 끝말잇기이다! 욱제와 준원이는 총 $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$는 알파벳 소문자로만 구성된 팰린드롬 문자열이다.

예제 입력 1

3
pqqp pqpqp pbbbp

예제 출력 1

1

주어진 문자열을 어떤 순서로 나열하더라도 p로 시작하거나 p로 끝나므로 끝말잇기를 진행할 수 있다.

예제 입력 2

3
aba c dd

예제 출력 2

0

주어진 문자열을 어떤 순서로 나열하더라도 끝말잇기를 할 수 없다.

출처

Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2020! A번