Little X has n distinct integers: p_1, p_2, ..., p_{n}. He wants to divide all of them into two sets A and B. The following two conditions must be satisfied:  If number x belongs to set A, then number a - x must also belong to set A.  If number x belongs to set B, then number b - x must also belong to set B. 

Help Little X divide the numbers into two sets or determine that it's impossible.


-----Input-----

The first line contains three space-separated integers n, a, b (1 ≤ n ≤ 10^5; 1 ≤ a, b ≤ 10^9). The next line contains n space-separated distinct integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ 10^9).


-----Output-----

If there is a way to divide the numbers into two sets, then print "YES" in the first line. Then print n integers: b_1, b_2, ..., b_{n} (b_{i} equals either 0, or 1), describing the division. If b_{i} equals to 0, then p_{i} belongs to set A, otherwise it belongs to set B.

If it's impossible, print "NO" (without the quotes).


-----Examples-----
Input
4 5 9
2 3 4 5

Output
YES
0 0 1 1

Input
3 3 4
1 2 4

Output
NO



-----Note-----

It's OK if all the numbers are in the same set, and the other one is empty.

Source: codeforces | Difficulty: HARD
Tags: Graph traversal

Strong connectivity

Greedy algorithms

Flows and cuts

Spanning trees


Solutions:
parent = []
ranks = []

def make_set(n):
	nonlocal parent, ranks
	parent = [i for i in range(n + 5)]
	ranks = [0 for i in range(n + 5)]

def find_set(u):
	if parent[u] != u:
		parent[u] = find_set(parent[u])
	else:
		parent[u] = u
	return parent[u]

def union_set(u, v):
	up = find_set(u)
	vp = find_set(v)
	if ranks[up] > ranks[vp]:
		parent[vp] = up
	elif ranks[up] < ranks[vp]:
		parent[up] = vp
	else:
		parent[up] = vp
		ranks[vp] += 1

def solution():
	set_indicators = dict()
	(n, a, b) = list(map(int, input().split()))
	numbers = list(map(int, input().split()))
	A = n + 1
	B = A + 1
	make_set(n)
	for i in range(n):
		set_indicators[numbers[i]] = i
	for i in range(n):
		if set_indicators.get(a - numbers[i]) is not None:
			union_set(i, set_indicators.get(a - numbers[i]))
		else:
			union_set(i, B)
		if set_indicators.get(b - numbers[i]) is not None:
			union_set(i, set_indicators.get(b - numbers[i]))
		else:
			union_set(i, A)
	if find_set(A) == find_set(B):
		print('NO')
		return
	print('YES')
	print(''.join(('1 ' if find_set(i) == find_set(n + 2) else '0 ' for i in range(n))))
solution()


MAX = 100001
parent = []

def makeSet():
	global parent
	parent = [i for i in range(MAX + 1)]

def findSet(u):
	global parent
	if u != parent[u]:
		parent[u] = findSet(parent[u])
	return parent[u]

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	parent[up] = vp
makeSet()
(n, a, b) = map(int, input().split())
p = list(map(int, input().split()))
pos = dict()
for i in range(n):
	pos[p[i]] = i + 1
for i in range(n):
	unionSet(i + 1, pos.get(a - p[i], n + 1))
	unionSet(i + 1, pos.get(b - p[i], 0))
A = findSet(0)
B = findSet(n + 1)
if A != B:
	print('YES')
	for i in range(1, n + 1):
		if findSet(i) == B:
			print('1', end=' ')
		else:
			print('0', end=' ')
else:
	print('NO')


def find(u):
	nonlocal par
	if u != par[u]:
		par[u] = find(par[u])
	return par[u]

def union(u, v):
	u = find(u)
	v = find(v)
	par[u] = v
(n, a, b) = map(int, input().split())
p = list(map(int, input().split()))
mp = dict()
for i in range(n):
	mp[p[i]] = i + 1
par = [i for i in range(n + 2)]
for i in range(n):
	union(i + 1, mp.get(a - p[i], n + 1))
	union(i + 1, mp.get(b - p[i], 0))
A = find(0)
B = find(n + 1)
if A != B:
	print('YES')
	print(' '.join(['1' if find(i) == B else '0' for i in range(1, n + 1)]))
else:
	print('NO')


class DisjointSet:

	def __init__(self, n):
		self._fa = list(range(n))

	def union(self, x, y):
		x = self.get_father(x)
		y = self.get_father(y)
		self._fa[x] = y
		return y

	def get_father(self, x):
		y = self._fa[x]
		if self._fa[y] == y:
			return y
		else:
			z = self._fa[y] = self.get_father(y)
			return z

	def __repr__(self):
		return repr([self.get_father(i) for i in range(len(self._fa))])

def solve(n, a, b, xs):
	h = {x: i for (i, x) in enumerate(xs)}
	if a == b:
		if all((a - x in h for x in xs)):
			return [0] * n
		return False
	g1 = n
	g2 = n + 1
	ds = DisjointSet(n + 2)
	for (i, x) in enumerate(xs):
		for t in (a, b):
			if t - x in h:
				ds.union(i, h[t - x])
	for (i, x) in enumerate(xs):
		b1 = a - x in h
		b2 = b - x in h
		if b1 + b2 == 0:
			return False
		if b1 + b2 == 1:
			if b1:
				ds.union(i, g1)
			else:
				ds.union(i, g2)
			if ds.get_father(g1) == ds.get_father(g2):
				return False
	group = [None] * n
	for (i, x) in enumerate(xs):
		f = ds.get_father(i)
		if f < n:
			return False
		group[i] = f - n
	return group
(n, a, b) = list(map(int, input().split()))
xs = list(map(int, input().split()))
group = solve(n, a, b, xs)
if isinstance(group, list):
	print('YES')
	print(' '.join(map(str, group)))
else:
	print('NO')


from sys import setrecursionlimit
import threading
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 26)

def ind(x):
	global index
	if x in index:
		return index[x]
	else:
		return -1

def dfs(u, cur):
	global used, comps, cmp, a, p, b
	used[u] = True
	comps[cur].append(u)
	cmp[u] = cur
	for v in (ind(a - p[u]), ind(b - p[u])):
		if v != -1 and (not used[v]):
			dfs(v, cur)

def main():
	global used, comps, cmp, a, p, b, index
	(n, a, b) = map(int, input().split())
	p = list(map(int, input().split()))
	index = dict()
	for i in range(n):
		index[p[i]] = i
	used = [False] * n
	comps = []
	cmp = [0] * n
	cur = 0
	for i in range(n):
		if not used[i]:
			comps.append([])
			dfs(i, cur)
			cur += 1
	col = [-1] * len(comps)
	for i in range(n):
		if ind(a - p[i]) != -1 and ind(b - p[i]) == -1:
			if col[cmp[i]] == 1:
				print('NO')
				exit()
			else:
				col[cmp[i]] = 0
		if ind(a - p[i]) == -1 and ind(b - p[i]) != -1:
			if col[cmp[i]] == 0:
				print('NO')
				exit()
			else:
				col[cmp[i]] = 1
		if ind(a - p[i]) == -1 and ind(b - p[i]) == -1:
			print('NO')
			exit()
	for i in range(len(col)):
		if col[i] == -1:
			col[i] = 0
	print('YES')
	for i in range(n):
		print(col[cmp[i]], end=' ')
thread = threading.Thread(target=main)
thread.start()


from collections import defaultdict

def solve(n, a, b, xs):
	group = [None] * n
	id_ = {x: i for (i, x) in enumerate(xs)}
	if a == b:
		for x in xs:
			if a - x not in id_:
				return False
		group = [0] * n
	else:
		for (i, x) in enumerate(xs):
			if group[i] is not None:
				continue
			y = a - x
			z = b - x
			f1 = y in id_ and group[id_[y]] is None
			f2 = z in id_ and group[id_[z]] is None
			if f1 + f2 == 0:
				return False
			elif f1 + f2 == 1:
				g = int(f2)
				link = []
				t = a if f1 else b
				while x in id_:
					link.append(x)
					x = t - x
					if x + x == t:
						break
					t = a + b - t
				if len(link) % 2 == 0:
					for (i, x) in enumerate(link):
						group[id_[x]] = g
				elif link[0] * 2 == (b, a)[g]:
					for (i, x) in enumerate(link):
						group[id_[x]] = 1 - g
				elif link[-1] * 2 == (a, b)[g]:
					for (i, x) in enumerate(link):
						group[id_[x]] = g
				else:
					return False
	return group
(n, a, b) = map(int, input().split())
xs = list(map(int, input().split()))
group = solve(n, a, b, xs)
if isinstance(group, list):
	print('YES')
	print(' '.join(map(str, group)))
else:
	print('NO')


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, a, b) = I()
l = I()
dic = dd(int)
for i in range(n):
	dic[l[i]] = 1
bs = []
pa = dd(int)
for i in range(n):
	if dic[a - l[i]] == 0:
		bs.append(l[i])
	else:
		pa[l[i]] = a - l[i]
j = 0
while j < len(bs):
	for i in range(j, len(bs)):
		cr = bs[i]
		dic[cr] = 2
		if dic[b - cr] == 0:
			print('NO')
			return
		dic[b - cr] = 2
		if dic[a - b + cr] == 1:
			dic[a - b + cr] = 2
			bs.append(a - b + cr)
		j += 1
an = [0] * n
for i in range(n):
	an[i] = dic[l[i]] - 1
print('YES')
print(*an)


parent = [i for i in range(100002)]

def findSet(u):
	if parent[u] != u:
		parent[u] = findSet(parent[u])
	return parent[u]

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	parent[up] = vp
(n, a, b) = map(int, input().split())
lst = list(map(int, input().split()))
temp = {lst[i]: i for i in range(n)}
for i in range(n):
	if a - lst[i] in temp:
		unionSet(i, temp[a - lst[i]])
	else:
		unionSet(i, n)
	if b - lst[i] in temp:
		unionSet(i, temp[b - lst[i]])
	else:
		unionSet(i, n + 1)
pa = findSet(n)
pb = findSet(n + 1)
if pa == pb:
	print('NO')
else:
	print('YES')
	lst = [0 if findSet(i) == pb else 1 for i in range(n)]
	print(*lst)


def findSet(u):
	if parents[u] != u:
		parents[u] = findSet(parents[u])
	return parents[u]

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	if up == vp:
		return
	if ranks[up] > ranks[vp]:
		parents[vp] = up
	elif ranks[up] < ranks[vp]:
		parents[up] = vp
	else:
		parents[up] = vp
		ranks[vp] += 1
(n, a, b) = map(int, input().split())
ps = list(map(int, input().split()))
mapping = set(ps)
parents = {x: x for x in ps}
parents['A'] = 'A'
parents['B'] = 'B'
ranks = {x: 0 for x in ps}
ranks['A'] = 0
ranks['B'] = 0
result = True
for x in ps:
	if a - x in mapping:
		unionSet(x, a - x)
	else:
		unionSet(x, 'B')
	if b - x in mapping:
		unionSet(x, b - x)
	else:
		unionSet(x, 'A')
if findSet('A') == findSet('B'):
	print('NO')
else:
	print('YES')
	for i in ps:
		if findSet(i) == findSet('A'):
			print('0', end=' ')
		else:
			print('1', end=' ')


import sys
import queue
sys.setrecursionlimit(100000)
INF = int(10000000.0 + 1)
MAX = 100005
parents = []
ranks = []
size = []
n = 0

class Pair:

	def __init__(self, a, b):
		self.first = a
		self.second = b

def init():
	global parents, ranks, size
	parents = [i for i in range(n + 2)]
	ranks = [0 for i in range(n + 2)]
	size = [1 for i in range(n + 2)]

def findSet(u):
	if parents[u] != u:
		parents[u] = findSet(parents[u])
	return parents[u]

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	if up == vp:
		return
	if ranks[up] < ranks[vp]:
		parents[up] = vp
	elif ranks[vp] < ranks[up]:
		parents[vp] = up
	else:
		ranks[vp] += 1
		parents[up] = vp

def main():
	global n
	(n, a, b) = map(int, input().split())
	init()
	M = {}
	l = list(map(int, input().split()))
	Max = -1
	l.insert(0, -1)
	l.append(-1)
	for i in range(1, n + 1):
		M[l[i]] = i
		parents[i] = i
		Max = max(Max, l[i])
	if Max >= a and Max >= b:
		print('NO')
		return
	for i in range(1, n + 1):
		if a - l[i] in M:
			unionSet(M[a - l[i]], i)
		else:
			unionSet(i, n + 1)
		if b - l[i] in M:
			unionSet(M[b - l[i]], i)
		else:
			unionSet(i, 0)
	A = findSet(0)
	B = findSet(n + 1)
	if A == B:
		print('NO')
		return
	print('YES')
	for i in range(1, n + 1):
		if findSet(i) == A:
			print('%d' % 0, end=' ')
		else:
			print('%d' % 1, end=' ')
main()


def process(X, a, b):
	X1 = set(X)
	Other = set([])
	A = set([])
	B = set([])
	Both = set([])
	for x in X:
		if a - x in X1 and b - x not in X1:
			A.add(x)
			A.add(a - x)
		elif a - x not in X1 and b - x in X1:
			B.add(x)
			B.add(b - x)
		elif a - x not in X1 and b - x not in X1:
			return 'NO'
		else:
			Both.add(x)
	start = A.copy()
	while len(start) > 0:
		next_s = set([])
		for x in start:
			if b - x in Both:
				Both.remove(b - x)
				next_s.add(b - x)
				if a - b + x in Both:
					Both.remove(a - b + x)
					A.add(a - b + x)
					next_s.add(a - b + x)
				A.add(b - x)
			if a - x in Both:
				Both.remove(a - x)
				next_s.add(a - x)
				A.add(a - x)
			elif a - x in B or a - x not in A:
				return 'NO'
		start = next_s
	start = B.copy()
	while len(start) > 0:
		next_s = set([])
		for x in start:
			if a - x in Both:
				Both.remove(a - x)
				next_s.add(a - x)
				if b - a + x in Both:
					Both.remove(b - a + x)
					B.add(b - a + x)
					next_s.add(b - a + x)
				B.add(a - x)
			if b - x in Both:
				Both.remove(b - x)
				next_s.add(b - x)
				B.add(b - x)
			elif b - x in A or b - x not in B:
				return 'NO'
		start = next_s
	answer = []
	for x in X:
		if x in A:
			answer.append(0)
		else:
			answer.append(1)
	return answer
(n, a, b) = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
answer = process(X, a, b)
if answer == 'NO':
	print('NO')
else:
	print('YES')
	print(' '.join(map(str, answer)))


parent = [i for i in range(int(100000.0 + 10))]

def findSet(u):
	if parent[u] != u:
		parent[u] = findSet(parent[u])
	return parent[u]

def unionSet(u, v):
	up = findSet(u)
	vp = findSet(v)
	parent[up] = vp
(n, a, b) = map(int, input().split())
lst = list(map(int, input().split()))
temp = {lst[i]: i for i in range(n)}
for i in range(n):
	if a - lst[i] in temp:
		unionSet(i, temp[a - lst[i]])
	else:
		unionSet(i, n)
	if b - lst[i] in temp:
		unionSet(i, temp[b - lst[i]])
	else:
		unionSet(i, n + 1)
if findSet(n) == findSet(n + 1):
	print('NO')
else:
	print('YES')
	tmp = findSet(n + 1)
	lst = [0 if findSet(i) == tmp else 1 for i in range(n)]
	print(*lst)


class UnionFind:

	def __init__(self, n):
		self.parent = [i for i in range(n + 2)]
		self.rank = [0 for i in range(n + 2)]

	def union(self, u, v):
		up = self.find(u)
		vp = self.find(v)
		if up == vp:
			return
		if self.rank[up] == self.rank[vp]:
			self.parent[up] = vp
			self.rank[vp] += 1
		elif self.rank[up] < self.rank[vp]:
			self.parent[up] = vp
		else:
			self.parent[vp] = up

	def find(self, u):
		if u != self.parent[u]:
			self.parent[u] = self.find(self.parent[u])
		return self.parent[u]
(n, a, b) = map(int, input().split())
nums = list(map(int, input().split()))
numToIndex = {}
for (i, num) in enumerate(nums):
	numToIndex[num] = i
uf = UnionFind(n)
for (i, num) in enumerate(nums):
	complA = a - num
	if complA in numToIndex:
		uf.union(i, numToIndex[complA])
	else:
		uf.union(i, n + 1)
	complB = b - num
	if complB in numToIndex:
		uf.union(i, numToIndex[complB])
	else:
		uf.union(i, n)
setA = uf.find(n)
setB = uf.find(n + 1)
if setA == setB:
	print('NO')
else:
	print('YES')
	ans = []
	for i in range(n):
		if uf.find(i) == uf.find(n):
			ans.append('0')
		else:
			ans.append('1')
	print(' '.join(ans))