Unique Dice

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

요약

각 줄에 주사위 여섯 면의 숫자가 주어질 때, 회전해도 같은 주사위끼리 묶었을 때 가장 큰 무리의 크기를 구한다.

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

문제

You are about to leave home for your weekly game of Pumpkins and Flagons (P&F) when a text comes in asking you to bring a large collection of identical P&F dice. They have asked the right person, for you have a very large collection of P&F dice which, unfortunately, is currently unsorted.

These dice are ordinary cubes with a number on each of the six faces. The numbers are in the range 1–6, but they do not need to be distinct. For example, $\\{ 1, 2, 3, 4, 5, 6\\}$ , $\\{ 1, 1, 1, 1, 1, 1\\}$ and $\\{ 2, 2, 2, 4, 4, 5\\}$ are all valid sets of numbers for the six faces. For this problem you want to find the size of the largest set of identical dice you can create from your very large collection. Two dice are considered identical to each other if it is possible to rotate one of the dice so that their top numbers are the same, their bottom numbers are the same, and so on for all six faces.

Figure 1: The six faces of a die.

입력

The first line contains an integer $n$ $( 1 \leq n \leq 500\\, 000)$ , indicating the number of dice in your collection. The next $n$ lines each contains six integers in the range $1$ – $6$ , separated by spaces, giving, in order, the numbers that appears on the top, bottom, front, back, left and right faces (see Figure 1).

출력

Print a single integer giving the size of the largest set of identical dice that can be made from given collection.

예제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

예상 출력