April Fools
시간 제한1초메모리 제한1024 MB
N개 신문이 각각 목록에서 거짓 사실을 하나씩 실었을 때, 거짓일 수 있는 사실 개수의 최솟값과 최댓값을 구한다.
문제
On April Fools Day newspapers like to fool their readers by publishing false and usually absurd facts. For example, a fact stating that today Vilnius television tower was brought down by wind.
You are given a range of facts which were published by each of the N different newspapers. These facts are denoted by natural numbers from 1 to F. For example:
- Newspaper 1: 1, 2, 5
- Newspaper 2: 2, 3, 4
- Newspaper 3: 1, 6
You also know that this April Fools Day each of the newspapers published exactly one false fact.
Find the smallest and the biggest number of false facts that could have been published today.
입력
The first line of the input contains two integer numbers separated by a space: the number of newspapers N and the number of facts F.
Facts published by each of the newspapers are described on the remaining 2N lines.
On the 2ith line there is given the number ki – it is the number of facts published by the ith newspaper (1 ≤ ki ≤ F).
On the (2i+ 1)th line there are given ki integer numbers fij separated by spaces, 1 ≤ fij ≤ F, fij < fi(j+1). All of the facts from 1 to F are published at least once by at least one of the newspapers.
출력
On the first and only line, output two numbers separated by space: the smallest and the biggest number of false facts that could have been published that day.
제한
- 1 ≤ N ≤ 200
- 1 ≤ F ≤ 20