화장품 선호도 조사

ICP(International Cosmetic Perfection) Company는 새로 출시한 m개의 화장품 중 어느 것이 가장 선호되는지 알아보기 위해 선호도 조사를 계획한다. 이 조사를 위해 ICPC는 n명의 평가자를 선정했다. 각 평가자는 m개의 화장품에 대한 선호 순서 목록을 제출해야 한다. 각 평가자는 다음과 같이 화장품의 순위를 매길 수 있다.

• 평가자는 화장품에 양의 정수로 순위를 매길 수 있지만, 양의 정수가 반드시 연속일 필요는 없다. 가장 작은 양의 정수를 받은 화장품이 가장 선호되는 것이고, 두 번째로 작은 양의 정수를 받은 화장품이 두 번째로 선호되는 것, 이런 식으로 이어진다.
• 평가자는 여러 화장품에 같은 선호도를 줄 수 있다. 이는 평가자가 그 화장품들 사이에 선호 차이가 없음을 나타낸다.
• 평가자는 일부 화장품에 순위를 매기지 않을 수 있다. 순위를 매기지 않은 화장품은 순서 목록에서 숫자 0으로 표시된다. 이는 평가자가 순위를 매긴 모든 화장품을 순위를 매기지 않은 모든 화장품보다 엄격하게 선호하며, 순위를 매기지 않은 화장품들 사이에는 선호 차이가 없음을 나타낸다.

예를 들어, 오른쪽 그림은 한 평가자가 여섯 개의 화장품 A, B, C, D, E, F에 대해 제출한 선호 순서 목록을 보여준다. 화장품 A, C, E, F는 각각 1, 4, 1, 3이라는 연속되지 않은 정수로 순위가 매겨졌다. 나머지 두 화장품 B와 D는 순위가 매겨지지 않아 0으로 표시되었다. A와 E는 같은 선호도를 가지며, 선호도 값이 가장 작은 양의 정수이므로 가장 선호되는 화장품이다. 순위가 매겨지지 않은 B와 D는 순위가 매겨진 것들보다 덜 선호된다. 결과적으로 이 평가자의 선호 순서는 A = E ≻ F ≻ C ≻ B = D이며, 여기서 X ≻ Y는 X가 Y보다 엄격하게 선호됨을, X = Y는 선호도가 같음을 의미한다.

이 선호도 조사에서 n명의 평가자가 가장 선호하는 화장품은 무엇인가? 이제 어느 것이 다른 것보다 선호되는지 정의해야 한다. d(X, Y)를 X를 Y보다 엄격하게 선호하는 평가자의 수라고 하자. X에서 Y로의 경로는 C1 = X, Ck = Y이고 모든 t = 1, ... , k − 1에 대해 d(Ct, Ct+1) > d(Ct+1, Ct)인 서로 다른 화장품의 수열 C1, ..., Ck이다. 이 경로의 선호 지수는 1 ≤ t < k에 대한 d(Ct, Ct+1)의 최솟값으로 정의된다. X에서 Y로의 경로로 연결된 서로 다른 두 화장품 X와 Y에 대해, 선호 강도 S(X,Y)는 X에서 Y로의 모든 경로에 대한 선호 지수의 최댓값이다. X에서 Y로의 경로가 없으면 S(X,Y)는 0으로 정의된다. 화장품 X가 이 조사에서 가장 선호되는 화장품 중 하나라는 것은 X가 아닌 모든 Y에 대해 S(X,Y) ≥ S(Y,X)라는 것과 필요충분조건이다. 이런 종류의 조사에서는 가장 선호되는 화장품이 적어도 하나는 항상 존재한다는 것이 알려져 있다.

m개의 화장품에 대한 n명의 평가자의 선호 목록이 주어질 때, 가장 선호되는 화장품을 모두 출력하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 읽는다. 입력은 두 정수 m과 n (1 ≤ m ≤ 500, 1 ≤ n ≤ 500)을 포함하는 한 줄로 시작하며, 여기서 m은 화장품의 수이고 n은 평가자의 수이다. 화장품은 1부터 m까지, 평가자는 1부터 n까지 번호가 매겨진다. 다음 n개의 줄에서 i번째 줄은 평가자 i의 m개 화장품에 대한 선호 값을 나타내는 m개의 음이 아닌 정수를 포함한다. 선호 값은 화장품 1부터 화장품 m까지의 순서로 나열된다. 목록에서 0인 값은 평가자가 해당 화장품에 순위를 매기지 않았음을 의미한다. 선호 값은 106 이하이다.

프로그램은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 이 줄은 가장 선호되는 화장품의 번호를 포함해야 한다. 이러한 화장품 번호는 증가하는 순서로 나타나야 한다.