만우절

면접 대비

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

요약

각 신문이 틀린 사실을 정확히 하나씩 낸다고 할 때, 그날 발표된 틀린 사실의 최소 개수와 최대 개수를 구합니다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 비트 연산
정답자: 아직 제출이 없습니다

문제

만우절에는 신문사들이 독자를 속이려고 거짓이고 대개 터무니없는 사실을 실곤 합니다. 예를 들어, 오늘 빌뉴스의 텔레비전 송신탑이 바람에 쓰러졌다는 사실이 있습니다.

$N$ 개의 서로 다른 신문사가 각각 실은 사실들의 범위가 주어집니다. 사실은 $1$ 부터 $F$ 까지의 자연수로 표시됩니다. 예를 들면 다음과 같습니다.

신문사 1: 1, 2, 5
신문사 2: 2, 3, 4
신문사 3: 1, 6

이번 만우절에 각 신문사는 거짓 사실을 정확히 하나씩 실었다는 것도 알고 있습니다.

오늘 실렸을 수 있는 거짓 사실의 최소 개수와 최대 개수를 구하세요.

입력

첫 번째 줄에 두 정수 $N$ 과 $F$ 가 공백으로 구분되어 주어집니다.

나머지 $2N$ 개 줄에 각 신문사가 실은 사실이 주어집니다. $2i$ 번째 줄에는 $i$ 번째 신문사가 실은 사실의 개수 $k_i$ 가 주어집니다 ( $1 \le k_i \le F$ ). $2i+1$ 번째 줄에는 $k_i$ 개의 정수 $f_{ij}$ 가 공백으로 구분되어 주어집니다. 여기서 $1 \le f_{ij} \le F$ 이고 $f_{ij} < f_{i(j+1)}$ 입니다. $1$ 부터 $F$ 까지의 모든 사실은 적어도 한 신문사가 실었습니다.

출력

한 줄에 공백으로 구분하여 두 수를 출력합니다. 첫 번째 수는 오늘 실렸을 수 있는 거짓 사실 개수의 최솟값이고, 두 번째 수는 최댓값입니다.

제한

$1 \le N \le 200$
$1 \le F \le 20$

예제1

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