Informatica Online Judge

  Hope [0637 / 027D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 6   Total Tried : 45


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

최근 해외여행을 하고 돌아온 iami9999는 희망전도사가 되어 주변사람들에게 일본 담배 희망(HOPE)를 나누어준다.

하지만 국내로 들어오며 들고 올 수 있는 희망의 개수는 많지 않기 때문에 이것만을 나누어 주는 것으로는 진정한 희망전도사가 되기 힘들다는 것을 깨닫고, 대단한 기적을 보여 모든 사람들에게 어떤 불가능해 보이는 일이든 사실은 그게 가능하다는 희망을 보여주기로 마음먹었다.

iami9999가 고안한 기적은 다음과 같다.

m*n개의 카드에 각각 숫자 1<=i<=m을 n개씩 쓰고, 이 m*n개의 카드를 잘 섞는다. 그리고 이 카드들을 n장씩 m개의 더미로 나누고, 각 더미마다 한 장씩의 카드를 잘 뽑아 (뒤의 숫자는 관계없이)앞 숫자들이 1부터 m까지 각각의 숫자가 쓰인 카드가 정확히 한 장이 되도록 뽑는다.(예를 들어 m=13, n=4인 경우에는 트럼프카드가 된다.)

iami9999는 고민이 생겼다. 이러한 기적이 과연 가능하기나 한 것일까? 그래서 일단 카드를 마구 섞은 이후 당신에게 이 기적을 시행하는 방법을 문의하기로 했다.

Input

첫 번째 줄에 자연수 m과 n이 순서대로 입력된다.
(m <= 3000, n <= 100)
2번째 줄부터 m+1번째 줄까지는 각 덱에 포함된 카드에 적힌 n개의 숫자 xi,j가 하나씩 입력된다. 각 숫자는 정확히 m번씩만 입력된다.

Output

첫 번째 덱부터 m번째 덱까지 뽑아야 하는 카드에 적힌 숫자의 쌍 m개를 출력한다.

IO Example

입력
5 2
1 2
2 3
3 4
4 5
5 1

출력
1 1
2 1
3 1
4 1
5 1

또는

2 2
3 2
4 2
5 2
1 5

중 아무거나 출력하면 된다.

출제 : 한민기 (서울대 수리과학부)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]