합집합
시간 제한2초메모리 제한1024 MB
정수 집합 n개가 주어질 때, 전체 합집합과 다른 부분집합의 합집합 중 원소 수가 최대인 것을 구한다.
문제
양의 정수로 구성된 집합 이 주어진다. 중 몇 개를 적당히 골라서, 그 합집합이 와 같아지게 할 수 있다면 를 생성 가능하다고 한다. 개를 선택할 수도 있기 때문에, 공집합은 항상 생성 가능하다.
집합 가 생성 가능하고, 일 때, 의 원소의 개수의 최댓값을 구하여라.
집합 의 합집합은 중 하나 이상에 포함된 수의 집합으로 정의하며, 와 같이 표기한다. 예를 들어, 이다.
입력
각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 가 주어진다(). 다음 줄부터 각각의 테스트 케이스가 주어진다.
각각의 테스트 케이스의 첫 번째 줄에 정수 이 주어진다 ().
다음 개의 줄에 의 정보가 주어진다. 이 중 번째 줄에는 의 원소의 개수 와 의 원소 가 공백으로 구분되어 주어진다 (, ).
출력
각각의 테스트 케이스마다 정답을 출력한다.
힌트
첫 번째 테스트 케이스에서, 일 때 원소 개수가 최대이다.
두 번째 테스트 케이스에서, 일 때 원소 개수가 최대이다.
세 번째 테스트 케이스에서, 일 때 원소 개수가 최대이다.
네 번째 테스트 케이스에서, 가능한 는 로 유일하다.