문자열 탑 쌓기

면접 대비

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

요약

길이가 M인 문자열 N개가 주어졌을 때, 각 문자열을 이전 문자열 위에 겹쳐 놓아 겹치는 부분이 일치하도록 순서대로 쌓을 수 있는지 판단합니다.

문제

인경이는 $N$ 개의 문자열을 쌓아 문자열 탑을 완성하려고 한다. 탑을 완성하려면 모든 문자열을 한 층에 하나씩 아래에서부터 순서대로 쌓아 올려야 한다.

인경이는 탑 꼭대기에 다음 순서의 문자열을 쌓을 수 있다. 단, 탑을 튼튼하게 만들려면 탑 꼭대기의 문자열과 새로 쌓을 문자열이 겹치는 부분이 완전히 같아야 한다. 가장 첫 문자열은 바닥에 아무렇게나 쌓을 수 있다.

예를 들어 abc 위에 cab를 쌓는다고 하면, 일부가 겹치게 쌓는 경우는 위 그림과 같이 5가지다. 그중에서 abc와 cab가 겹치는 부분이 완전히 같은 경우에만 쌓을 수 있다.

인경이가 문자열을 잘 쌓는다면 $N$ 개의 문자열을 순서대로 쌓아 문자열 탑을 완성하는 것이 가능할까?

첫째 줄에 문자열의 개수 $N(1\le N \le 100)$ 과 문자열의 길이 $M(1\le M \le 100)$ 이 주어진다.

둘째 줄부터 $N$ 개의 줄에 $s_1, s_2, ..., s_N$ 이 주어진다. $s_i$ 는 $i$ 번째로 쌓는 문자열이다. 주어지는 모든 문자열의 길이는 $M$ 이며, 알파벳 소문자로만 이루어져 있다.

모든 문자열을 순서대로 쌓아 탑을 완성할 수 있으면 1을, 그렇지 않으면 0을 출력한다.