유로쿨렌

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 농장의 순위표가 주어질 때, 점수 상위 3개 출품작을 구합니다. 그다음 서로 같은 점수를 주고받은 농장의 투표를 지우고 다시 구합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

$N$ 개의 소규모 가족 농장(OPG)이 유럽 최고의 쿨렌을 뽑는 투표에 참가한다. 번호는 1부터 $N$ 까지 매겨져 있다. 쿨렌을 소개하고 시식한 뒤 투표를 진행한다. 각 OPG는 나머지 $N-1$ 개의 OPG에 순위를 매긴다. 가장 좋다고 고른 쿨렌에 $N-1$ 점을 주고, 그다음 쿨렌에 $N-2$ 점을 준다. 이런 식으로 마지막 쿨렌에는 1점만 준다.

질문 1: 1위, 2위, 3위를 차지한 쿨렌을 만든 OPG의 번호를 출력하라. 점수가 같으면 번호가 작은 쿨렌이 앞선다.

그런데 자그레브의 유럽 쿨렌 위원 K.M.씨가 투표 결과를 한 번 더 살펴본다. 유럽은 OPG끼리 점수를 주고받는 상황을 좋아하지 않는다. 즉 OPG A가 OPG B에 X점을 주고, OPG B도 OPG A에 X점을 주는 경우다. 위원이 이런 경우를 찾으면 A와 B의 투표는 모두 지우고, 새 순위를 정할 때 세지 않는다. 두 OPG의 쿨렌은 목록에 그대로 남고 투표만 지워진다.

질문 2: 점수를 주고받은 OPG의 점수를 지운 뒤 1위, 2위, 3위를 차지한 쿨렌을 만든 OPG의 번호를 출력하라. 점수가 같으면 번호가 작은 쿨렌이 앞선다.

입력

첫 줄에 자연수 $N$ ( $3 \le N \le 1000$ )이 주어진다. 이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 OPG $i$ 가 순위를 매긴 쿨렌의 번호 $K_j$ 가 그 순서대로 $N-1$ 개 주어진다( $1 \le K_j \le N-1$ , $K_j \ne i$ ).

출력

첫 번째 줄에 질문 1의 답인 OPG 번호 3개를 출력한다. 두 번째 줄에 질문 2의 답인 OPG 번호 3개를 출력한다.

힌트

첫 번째 테스트 케이스 설명: OPG 1은 2점, OPG 2는 3점, OPG 3은 4점을 얻었다. OPG 1은 OPG 2에 1점을 주었고, OPG 2도 OPG 1에 1점을 주었다. 같은 방식으로 OPG 2는 OPG 3에 2점을, OPG 3은 OPG 2에 2점을 주었다. 세 OPG가 준 점수를 모두 지우면 모든 OPG가 0점이 되므로, 번호가 작은 순서대로 1, 2, 3이 된다.

예제3

예제 1
입력
```
3
3 2
3 1
2 1
```
예상 출력
```
3 2 1
1 2 3
```
예제 2
입력
```
4
2 3 4
3 4 1
2 4 1
2 1 3
```
예상 출력
```
2 3 4
2 3 1
```

예제 3

입력

예상 출력

4 5 1
1 4 5