합집합
면접 대비시간 제한2초메모리 제한1024 MB
양의 정수 집합 n개가 주어졌을 때, 전체 합집합과 다르면서 일부 집합의 합집합으로 만들 수 있는 집합의 원소 개수 최댓값을 구합니다.
문제
양의 정수로 이루어진 집합 이 주어진다. 중 일부를 골라 그 합집합이 와 같아질 수 있으면 를 생성 가능하다고 한다. 0개를 고를 수도 있으므로 공집합은 항상 생성 가능하다.
가 생성 가능하고 일 때, 의 원소 개수의 최댓값을 구하여라.
집합 의 합집합은 중 하나 이상에 속하는 수들의 집합이며, 로 표기한다. 예를 들어 {2, 4, 6} \cup {2, 3} \cup {3, 6, 7} = {2, 3, 4, 6, 7}이다.
입력
첫 줄에 테스트 케이스의 개수 가 주어진다(). 각 테스트 케이스의 첫 줄에는 정수 이 주어진다(). 다음 개의 줄에 의 정보가 주어진다. 번째 줄에는 의 원소 개수 와 원소 가 공백으로 구분되어 주어진다(, ).
출력
각 테스트 케이스마다 정답을 출력한다.
힌트
첫 번째 테스트 케이스에서는 일 때 원소 개수가 최대이다.
두 번째 테스트 케이스에서는 일 때 원소 개수가 최대이다.
세 번째 테스트 케이스에서는 일 때 원소 개수가 최대이다.
네 번째 테스트 케이스에서는 가능한 가 뿐이다.