시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB80252337.705%

문제

주헌이는 최근에 엑셀을 열심히 공부하고 있다. 엑셀의 아름다운 작동 방식에 감동 받은 주헌이는 본인이 직접 엑셀과 같은 '스프레드 시트'를 개발하기로 마음 먹게 된다. 주헌이가 직접 개발했기 때문에 실제 작동방식은 엑셀과 조금 다른 부분이 있다.

스프레드 시트에서 직사각형 격자 한 칸을 '셀이라고 부른다. 각 셀은 자신의 위치를 좌표로 나타낼 수 있다. 이때 열(row) 성분은 알파벳 대문자로 나타내며 행(column) 성분은 1이상의 정수로 나타낸다. 열 성분은 A부터 시작하여 한 칸씩 커질수록 B, C, D...Z 와 같은 알파벳 순서를 따른다. 또한 Z 다음에는 AA이며 그 이후에는 AB, AC...AZ, BA, BB, BC, ... BZ, CA, CB, ... ZZ 와 같이 알파벳 대문자 26개로 이루어진 26진법 규칙을 따른다.

이 스프레드 시트에서는 셀을 변수로 취급해서 수식을 작성할 수 있는데 이것을 우리는 셀을 '참조'한다고 얘기한다. 그리고 셀을 참조하는 과정에서 cycle이 발생하는 현상을 순환 참조라고 부른다. 순환 참조는 참조하는 대상이 서로 물려있어서 참조할 수 없는 상태를 말한다. 순환 참조는 데이터의 큰 문제를 야기할 수 있다. 그래서 주헌이는 스프레드 시트 내에 순환 참조가 존재하는지 판별하고자 한다.

열의 크기가 R, 행의 크기가 인 스프레드 시트에서 각 셀이 참조하고 있는 셀의 정보가 주어질 때, 순환참조가 존재하는지의 여부를 판별하여라.

이 문제에서 자기 자신을 참조하는 셀은 없으며, 각 셀은 최대 2개의 서로 다른 셀을 참조할 수 있다고 가정한다.

입력

첫째 줄에 열과 행의 크기 R, 가 각각 주어진다.(1 ≤ ≤ 999 , 1 ≤ C ≤ 702)

둘째 줄부터 스프레드 시트의 각 칸이 참조하는 셀의 좌표가 주어진다. 알파벳 대문자는 A부터 첫 번째 행을 나타내고, 정수는 1부터 첫 번째 열을 나타낸다.

셀의 좌표는 알파벳 대문자 한글자 또는 두글자와 1이상 999이하의 정수가 결합된 형태이다. 다시 말해 가장 왼쪽 위 셀의 좌표는 A1, 가장 왼쪽 아래 셀의 좌표는 A999,가장 오른쪽 위 셀의 좌표는 ZZ1, 가장 오른쪽 아래 셀의 좌표는 ZZ999이다. (문제 하단 Note의 <그림 5> 참고)

만약 두 개의 셀을 참조한다면 +로 구분해서 주어진다. 아무 셀도 참조하지 않는다면 . 으로 주어진다.

입력으로 주어진 셀의 범위보다 큰 좌표는 입력으로 주어지지 않는다.

출력

입력받은 스프레드 시트에 순환참조가 존재하면 "yes", 존재하지 않는다면 "no" 를 큰따옴표 없이 출력하여라.

예제 입력 1

3 3
A2 A1+C1 .
B1 . .
. . .

예제 출력 1

yes

<그림 1>

<그림 1>은 예제 1을 스프레드 시트 상에서 나타낸 것이다.

[A1, B1, A2]는 순환참조(cycle)를 이루고 있다.

예제 입력 2

3 3
B1 C1 .
A1 A2 .
. . .

예제 출력 2

no

<그림 2>

<그림 2>는 예제 2를 스프레드 시트 상에서 나타낸 것이다.

예제 2는 순환참조(cycle)를 이루고 있지 않다.

예제 입력 3

4 3
. A1 B1
. . .
B4 A3 .
B3 A4 .

예제 출력 3

yes

<그림 3>

<그림 3>은 예제 3을 스프레드 시트 상에서 나타낸 것이다.

예제 입력 4

2 3
B1 C1 A1
A1 . .

예제 출력 4

yes

<그림 4>

<그림 4>는 예제4를 스프레드 시트 상에서 나타낸 것이다.

예제 입력 5

2 3
. . .
. . .

예제 출력 5

no

노트

<그림 5>

<그림 5>는 = 99, = 702 일 때 스프레드 시트의 셀의 좌표를 나타낸 것이다.

출처

University > 아주대학교 > 2021 아주대학교 프로그래밍 경시대회 APC > Div.2 G번