멘토링 매칭

한과영에는 졸업생 선배들의 도움을 원하는 학생들이 많이 있다. 다행히도, 카이스트에는 학생들을 돕고자 하는 졸업생들이 많이 있다. 그래서 은하는 학생들이 도움을 받을 수 있게끔 한과영 학생들과 카이스트 학생들을 연결해 주는 멘토링 매칭 시스템을 만드려고 한다.

매칭 시스템은 시스템에 등록된 $N$명의 한과영 학생들과 $N$명의 카이스트 학생들을 일대일로 매칭시킨다. 한과영과 카이스트 학생들은 $1$번부터 $N$번까지의 학번을 가지고 있다.

$N$명의 한과영 학생들은 각자 한 명씩의 카이스트 학생과 연결된다. 두 명 이상의 한과영 학생들이 동일한 카이스트 학생과 연결되는 일은 없다. 또한 한과영 학생들은 각자 $N$명의 카이스트 학생들에 대한 선호도를 가지고 있다. 선호도가 같은 경우는 없다.

그런데, 카이스트 학생들은 과제 때문에 너어어어어무 피곤하기 때문에, 한과영 학생들에 대한 선호도를 오직 학번만 가지고 결정한다. 구체적으로, 자신의 학번과 어떤 한과영 학생의 학번의 차가 더 클수록, 그 학생을 더 선호하게 된다. 차가 같은 한과영 학생끼리는 학번이 더 작은 한과영 학생이 더 선호된다.

은하는 매칭이 stable matching이 되기를 원하지만 과제도 하고, 시험공부도 하고, 마인크래프트 건축도 하고, 리듬게임도 하느라 바쁘다. 은하가 stable matching을 이룰 수 있도록 도와주자!

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐서 정수가 $N$개씩 주어진다. 각 정수는 $1$ 이상 $N$ 이하이며, $i+1$번째 줄의 $k$번째 정수가 $j$라면 $i$번 한과영 학생은 $j$번 카이스트 학생을 $k$번째로 선호한다는 뜻이다.

첫 번째 줄에 $N$개의 정수들을 출력한다. $i$번째 정수가 $j$라면 $i$번 한과영 학생과 $j$번 카이스트 학생을 연결한다는 뜻이다.

답이 여러 개 존재한다면 아무거나 출력해도 상관없다.

• $1 \leq N \leq 20$

어떤 매칭에 대해, 어떤 연결되지 못한 두 학생의 쌍 $(i, j)$가 다음 조건을 만족할 때 unstable하다고 한다.

• $i$는 그의 파트너보다 $j$를 더 선호한다.
• $j$는 그의 파트너보다 $i$를 더 선호한다.

Stable matching이란 unstable한 쌍이 없는 매칭을 의미한다.