데이터베이스

피터는 관계형 데이터베이스 이론을 연구한다. 관계형 데이터베이스의 표(table)는 행(row)과 열(column)로 배열된 값들로 이루어진다.

데이터베이스가 따를 수 있는 정규형(normal form)은 여러 가지가 있다. 정규형은 데이터베이스 안의 데이터 중복을 최소화하기 위해 고안되었다. 예를 들어 도서관을 위한 데이터베이스 표는 책마다 하나의 행을 두고, 책 이름·책의 저자·저자의 이메일을 각각의 열로 가질 수 있다.

같은 저자가 여러 권의 책을 썼다면 이러한 표현은 명백히 중복을 포함한다. 이런 종류의 중복을 형식적으로 정의하기 위해 피터는 자신만의 정규형을 도입했다. 어떤 표가 피터 정규형(Peter's Normal Form, PNF)에 속한다는 것은, 서로 다른 두 행과 서로 다른 두 열을 골랐을 때 그 두 열의 값이 두 행에서 모두 같아지는 경우가 존재하지 않는 것과 필요충분조건이다.

위와 같은 도서관 표는 명백히 PNF가 아니다. 저자 이름 열과 이메일 열의 값이 서로 다른 두 행에서 똑같이 반복되기 때문이다. 그러나 저자마다 고유한 식별자를 부여하고 이 표를 두 개의 표로 나누면 — 하나는 책 이름과 저자 id를, 다른 하나는 저자 id·저자 이름·저자 이메일을 담도록 — 두 표 모두 PNF가 된다.

표가 주어질 때, 그 표가 PNF인지 아닌지 판정하여라.

첫째 줄에 표의 행 수 n과 열 수 m이 주어진다 (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 10). 이어지는 n개의 줄에는 표의 각 행이 주어진다. 각 행은 쉼표로 구분된 m개의 열 값으로 이루어진다. 열 값은 공백(ASCII 32)부터 물결표(ASCII 126)까지의 ASCII 문자로 구성되며, 쉼표(ASCII 44)는 포함하지 않는다. 값은 비어 있지 않고 앞뒤에 공백이 없다. 각 행은 (구분 쉼표를 포함하여) 최대 80자이다.

표가 PNF이면 한 줄에 YES를 출력한다.

PNF가 아니면 세 줄을 출력한다. 첫째 줄에는 NO를 출력한다. 둘째 줄에는 두 행 번호 r1과 r2 (r1 < r2)를, 셋째 줄에는 두 열 번호 c1과 c2 (c1 < c2)를 출력하되, r1행과 r2행에서 c1열의 값이 서로 같고 c2열의 값도 서로 같도록 한다. 이러한 조건을 만족하는 위반 사례가 여러 개일 수 있으므로, 튜플 (r1, r2, c1, c2)가 사전순으로 가장 작은 것 하나만 출력한다. 즉 먼저 r1을 최소화하고, 그다음 r2, 그다음 c1, 마지막으로 c2를 최소화한다.