아이스크림 샘플

시간 제한3초메모리 제한512 MB

요약

원형으로 늘어선 샘플 상자들이 있을 때, 브랜드 1부터 K까지 모두 포함하는 가장 짧은 연속 구간을 찾아 그 안의 샘플 총개수를 구한다.

난이도: 어려움10점 중 8점
유형: 슬라이딩 윈도우, 투 포인터, 배열, 구현
정답자: 아직 제출이 없습니다

문제

공원에는 아이스크림 가판대가 원형 경로를 따라 늘어서 있다. 손님이 어느 가판대에서 아이스크림을 사면 경로상 바로 다음 가판대에서 하루 동안 쓸 수 있는 할인권을 자동으로 받는다. 아무 가판대에서 출발해 할인권이 가리키는 다음 가판대를 계속 따라가면 결국 원형 경로를 한 바퀴 돌아 출발한 가판대로 되돌아온다.

가판대에서는 여러 브랜드의 아이스크림을 판다. 또 가판대마다 인기 브랜드의 작은 샘플을 담은 샘플 상자를 판다. 상자에 든 샘플 개수는 가판대에 따라 다르고, 어떤 브랜드를 담는지도 가판대마다 다를 수 있다. 모든 상자에는 한 가지 이상의 브랜드 샘플이 들어 있다. 같은 브랜드가 상자 안에 여러 개 들어 있을 수도 있고, 하나도 없을 수도 있다. 한 가판대는 한 종류의 샘플 상자만 팔기 때문에 그 가판대의 상자에 담긴 브랜드 구성은 항상 같다.

Quido와 Hugo는 이 할인 제도를 이용하려고 한다. 두 사람은 가판대 하나를 골라 출발한 뒤 할인권이 가리키는 방향으로 연속한 가판대를 차례로 방문하면서 방문하는 가판대마다 샘플 상자를 하나씩 산다. 목표는 1번부터 $K$ 번까지 모든 브랜드의 샘플을 적어도 하나씩 모으는 것이다. 동시에 위장이 감당할 수 있도록 사는 샘플의 총 개수를 최소로 하려고 한다. 방문 구간은 원형 경로의 끝을 지나 첫 가판대로 이어질 수 있고, 같은 가판대를 두 번 방문하지는 않는다.

입력

입력은 여러 테스트 케이스로 이루어지며 파일 끝까지 이어진다. 각 케이스의 첫 줄에는 두 정수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다 ( $1 \le N, K \le 10^6$ ). $N$ 은 가판대 수, $K$ 는 브랜드 수이고 브랜드에는 1번부터 $K$ 번까지 번호가 붙는다. 이어지는 $N$ 개 줄은 방문 순서대로 가판대를 하나씩 설명하며, 마지막 줄의 가판대 다음은 첫 줄의 가판대다. 각 줄에는 그 가판대의 샘플 상자에 든 모든 샘플의 브랜드 목록이 주어진다. 먼저 목록의 길이를 나타내는 양의 정수 $L$ 이 오고, 그 뒤에 정수 $L$ 개가 온다. 각 정수는 상자에 든 샘플 하나의 브랜드 번호다. 어떤 브랜드 번호는 어느 상자에도 들어 있지 않을 수 있다. 한 테스트 케이스에서 모든 가판대의 상자를 하나씩 다 사도 모이는 샘플은 $10^7$ 개를 넘지 않는다.

출력

각 테스트 케이스마다 1번부터 $K$ 번까지 모든 브랜드의 샘플을 하나 이상 얻으려면 Quido와 Hugo가 최소 몇 개의 샘플을 사야 하는지를 한 줄에 정수 하나로 출력한다. 연속한 가판대를 어떻게 골라도 모든 브랜드를 모을 수 없으면 -1을 출력한다.

예제10

예제 1

입력

예상 출력

4
3
-1

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

예제 5

입력

5 1
3 1 1 1
2 1 1
1 1
4 1 1 1 1
5 1 1 1 1 1

예상 출력

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

예제 9

입력

6 4
2 4 4
1 1
1 2
1 3
5 4 4 4 4 4
1 4

예상 출력

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