동일한 주사위

면접 대비

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

요약

주사위 n개의 여섯 면 숫자가 주어질 때, 회전하면 서로 같아지는 주사위 중 가장 많은 개수를 구합니다.

난이도: 보통10점 중 4점
유형: 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

주간 Pumpkins and Flagons (P&F) 게임에 가려고 집을 나서는데 문자가 온다. 같은 P&F 주사위를 많이 가져와 달라는 부탁이다. 마침 당신에게는 아주 많은 P&F 주사위가 있지만, 아직 분류하지 않은 상태다.

이 주사위들은 여섯 면마다 숫자가 하나씩 적힌 일반 정육면체다. 숫자는 1에서 6 사이이며, 서로 달라야 하는 것은 아니다. 예를 들어 $\{ 1, 2, 3, 4, 5, 6 \}$ , $\{ 1, 1, 1, 1, 1, 1 \}$ , $\{ 2, 2, 2, 4, 4, 5 \}$ 는 모두 여섯 면의 숫자로 가능한 집합이다. 가지고 있는 주사위로 만들 수 있는 같은 주사위 집합 중 가장 큰 크기를 구한다. 두 주사위는 한쪽을 회전해서 윗면, 아랫면, 네 측면의 숫자가 다른 쪽과 모두 같아지면 같은 주사위로 본다.

그림 1: 주사위의 여섯 면.

입력

첫 줄에 주사위의 개수 $n$ ( $1 \leq n \leq 500\,000$ )이 주어진다. 다음 $n$ 개의 줄에는 각각 1에서 6 사이의 정수 여섯 개가 공백으로 구분되어 주어진다. 순서대로 윗면, 아랫면, 앞면, 뒷면, 왼쪽 면, 오른쪽 면에 적힌 숫자다 (그림 1 참고).

출력

만들 수 있는 같은 주사위 집합 중 가장 큰 크기를 정수 하나로 출력한다.

예제3

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

예제 3

입력

5
1 1 2 2 2 2
1 2 1 2 2 2
1 2 2 1 2 2
1 2 2 2 1 2
1 2 2 2 2 1

예상 출력