String Tower

Interview

Time limit1sMemory limit512 MB

Summary

Given N strings of length M, decide whether each string can be placed on the previous one so that their overlapping parts match exactly.

Level: Easy3 of 10
Topics: String, Brute force
Solved: No attempts yet

Problem

Inkyung wants to build a string tower by stacking $N$ strings. To finish the tower, all strings must be stacked one per layer, in order from the bottom up.

Inkyung can place the next string on top of the tower. To keep the tower sturdy, the overlapping part of the top string and the new string must be exactly identical. The first string can be placed on the floor in any way.

For example, when stacking cab on top of abc, there are 5 ways to stack them with a partial overlap, as shown above. Only the case where the overlapping part of abc and cab is exactly identical can be stacked.

If Inkyung stacks carefully, is it possible to complete the tower by stacking the $N$ strings in order?

Input

The first line contains the number of strings $N(1\le N \le 100)$ and the length of each string $M(1\le M \le 100)$ .

From the second line, $N$ lines follow with $s_1, s_2, ..., s_N$ . $s_i$ is the string stacked $i$ -th. Every string has length $M$ and consists only of lowercase English letters.

Output

Print 1 if all strings can be stacked in order to complete the tower, otherwise print 0.

Examples2

Example 1
Input
```
4 3
abc
cab
bac
acb
```
Expected output
```
1
```
Example 2
Input
```
3 3
ice
eco
gym
```
Expected output
```
0
```