Propagation and Merging 2

Interview

Time limit2sMemory limit512 MB

Summary

Given a grid where each cell references zero, one, or two other cells, decide whether the reference graph contains a cycle.

Level: Medium4 of 10
Topics: Graph, DFS, Topological sort, Implementation
Solved: No attempts yet

Problem

Juheon has been studying Excel hard lately. Moved by the way Excel works, Juheon decides to develop a 'spreadsheet' of his own, similar to Excel. Because Juheon develops it himself, the actual behavior differs a little from Excel.

In the spreadsheet, one square of the rectangular grid is called a 'cell'. Each cell can be represented by coordinates. The row component is written with uppercase letters, and the column component is written with an integer of at least 1. The row component starts at A and follows alphabetical order, so each step up gives B, C, D...Z. After Z comes AA, and after that comes AB, AC...AZ, BA, BB, BC, ... BZ, CA, CB, ... ZZ, following base-26 rules with the 26 uppercase letters.

In this spreadsheet, a cell can be treated as a variable when writing a formula, and this is called 'referencing' a cell. A cycle that occurs while referencing cells is called a circular reference. A circular reference is a state in which the referenced targets are tied to each other and cannot be resolved. A circular reference can cause serious data problems. So Juheon wants to determine whether a circular reference exists in the spreadsheet.

Given a spreadsheet with R rows and C columns and the information about which cell each cell references, determine whether a circular reference exists.

In this problem, no cell references itself, and each cell may reference at most two different cells.

Input

The first line gives the number of rows and columns R, C. (1 ≤ R ≤ 999, 1 ≤ C ≤ 702)

From the second line, the coordinates of the cells referenced by each cell of the spreadsheet are given. The uppercase letter A denotes the first row, and the integer 1 denotes the first column.

A cell coordinate is a combination of one or two uppercase letters and an integer between 1 and 999. In other words, the top-left cell is A1, the bottom-left cell is A999, the top-right cell is ZZ1, and the bottom-right cell is ZZ999. (See <Figure 5> in the Note at the bottom.)

If a cell references two cells, they are separated by +. If it references no cell, it is given as ..

No coordinate larger than the range of cells given as input is given.

Output

Print "yes" if a circular reference exists in the given spreadsheet, and "no" otherwise, without the quotation marks.

Hint

Examples5

Example 1
Input
```
3 3
A2 A1+C1 .
B1 . .
. . .
```
Expected output
```
yes
```
Example 2
Input
```
3 3
B1 C1 .
A1 A2 .
. . .
```
Expected output
```
no
```
Example 3
Input
```
4 3
. A1 B1
. . .
B4 A3 .
B3 A4 .
```
Expected output
```
yes
```
Example 4
Input
```
2 3
B1 C1 A1
A1 . .
```
Expected output
```
yes
```
Example 5
Input
```
2 3
. . .
. . .
```
Expected output
```
no
```