# CSAcademy 23 E. No Prime Sum ( Bipartite Matching, Minimum Vertex Cover )

Round #23 (Div. 2 only)

2≤N≤2000
The elements of S are distinct integers between 1 and 10^5

O( V * E )

```np = [ False for i in range( int( 2e5 + 1 ) ) ]
for i in range( 2, len( np ), 1 ):
if np[ i ]: continue
for j in range( i + i, len( np ), i ):
np[ j ] = True

N = int( input() )
S = list( map( int, input().split() ) )

L = []
R = []
for i in range( N ):
if S[ i ] & 1:
L.append( S[ i ] )
else:
R.append( S[ i ] )

adj = [ [] for i in range( len( L ) ) ]
for i in range( len( L ) ):
for j in range( len( R ) ):
if not np[ L[ i ] + R[ j ] ]:

bf = [ -1 for i in range( len( R ) ) ]
gf = [ -1 for i in range( len( L ) ) ]
def find_mate( u, vis = None ):
global bf
global gf
if vis == None:
vis = [ False for i in range( len( R ) ) ]
for v in adj[ u ]:
if vis[ v ]: continue
vis[ v ] = True
if bf[ v ] == -1 or find_mate( bf[ v ], vis ):
bf[ v ] = u
gf[ u ] = v
return True
return False

match_cnt = 0
for i in range( len( L ) ):
if gf[ i ] != -1: continue
match_cnt += find_mate( i )

print( match_cnt )

vis_L = [ False for i in range( len( L ) ) ]
vis_R = [ False for i in range( len( R ) ) ]
def dfs_alternate( u, nowR ):
global vis_L
global vis_R
if not nowR:
for v in adj[ u ]:
if vis_R[ v ]: continue
if bf[ v ] == u: continue
vis_R[ v ] = True
dfs_alternate( v, True )
else:
if bf[ u ] == -1: return
vis_L[ bf[ u ] ] = True
dfs_alternate( bf[ u ], False )
for i in range( len( L ) ):
if gf[ i ] != -1: continue
if vis_L[ i ]: continue
vis_L[ i ] = True
dfs_alternate( i, False )

ans = []
for i in range( len( L ) ):
if vis_L[ i ]: continue
ans.append( L[ i ] )
for i in range( len( R ) ):
if not vis_R[ i ]: continue
ans.append( R[ i ] )
print( *ans )
```