멋진 부분집합

면접 대비

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

요약

N개의 정수(2 이상 10억 이하)에서 공약수가 1보다 큰 원소를 ceil(N/2)개 골라 출력합니다. 그런 부분집합이 없으면 NO를 출력합니다.

난이도: 보통10점 중 5점
유형: 정수론, 확률, 수학
정답자: 아직 제출이 없습니다

문제

KSA 학생들은 멋진 집합을 좋아한다. 멋진 집합이란 모든 원소의 최대공약수가 $1$ 보다 큰 정수들의 중복집합이다. 크기가 $N$ 인 중복집합이 주어졌을 때, 그 부분집합 가운데 크기가 $\left\lceil\cfrac{N}{2}\right\rceil$ 이면서 멋진 집합인 것을 찾아보자.

입력

첫 번째 줄에 정수 $N$ 이 주어진다.

두 번째 줄에 중복집합의 원소인 $N$ 개의 정수가 주어진다.

출력

첫 번째 줄에 멋진 집합이 존재하면 YES, 존재하지 않으면 NO를 출력한다.

멋진 집합이 존재하면 두 번째 줄에 그 집합에 속한 $\left\lceil\cfrac{N}{2}\right\rceil$ 개의 정수를 출력한다. 정답이 여러 개라면 아무거나 출력해도 된다. 원소를 출력하는 순서는 상관없다.

제한

$3 \leq N \leq 5 \times 10^{5}$
원소는 $2$ 이상 $10^{9}$ 이하의 정수이다.

예제2

예제 1
입력
```
4
2 3 4 5
```
예상 출력
```
YES
2 4
```
예제 2
입력
```
5
3 5 7 9 11
```
예상 출력
```
NO
```