Moriarty has trapped n people in n distinct rooms in a hotel. Some rooms are locked, others are unlocked. But, there is a condition that the people in the hotel can only escape when all the doors are unlocked at the same time. There are m switches. Each switch control doors of some rooms, but each door is controlled by exactly two switches.

You are given the initial configuration of the doors. Toggling any switch, that is, turning it ON when it is OFF, or turning it OFF when it is ON, toggles the condition of the doors that this switch controls. Say, we toggled switch 1, which was connected to room 1, 2 and 3 which were respectively locked, unlocked and unlocked. Then, after toggling the switch, they become unlocked, locked and locked.

You need to tell Sherlock, if there exists a way to unlock all doors at the same time.


-----Input-----

First line of input contains two integers n and m (2 ≤ n ≤ 10^5, 2 ≤ m ≤ 10^5) — the number of rooms and the number of switches.

Next line contains n space-separated integers r_1, r_2, ..., r_{n} (0 ≤ r_{i} ≤ 1) which tell the status of room doors. The i-th room is locked if r_{i} = 0, otherwise it is unlocked.

The i-th of next m lines contains an integer x_{i} (0 ≤ x_{i} ≤ n) followed by x_{i} distinct integers separated by space, denoting the number of rooms controlled by the i-th switch followed by the room numbers that this switch controls. It is guaranteed that the room numbers are in the range from 1 to n. It is guaranteed that each door is controlled by exactly two switches.


-----Output-----

Output "YES" without quotes, if it is possible to open all doors at the same time, otherwise output "NO" without quotes.


-----Examples-----
Input
3 3
1 0 1
2 1 3
2 1 2
2 2 3

Output
NO
Input
3 3
1 0 1
3 1 2 3
1 2
2 1 3

Output
YES
Input
3 3
1 0 1
3 1 2 3
2 1 2
1 3

Output
NO


-----Note-----

In the second example input, the initial statuses of the doors are [1, 0, 1] (0 means locked, 1 — unlocked).

After toggling switch 3, we get [0, 0, 0] that means all doors are locked.

Then, after toggling switch 1, we get [1, 1, 1] that means all doors are unlocked.

It can be seen that for the first and for the third example inputs it is not possible to make all doors unlocked.

Difficulty: HARD
Tags: Spanning trees

Graph algorithms

Graph traversal

Strong connectivity

Starter code:

Solutions:
import sys
from collections import deque

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None

def solve():
	(n, m) = map(int, sys.stdin.readline().split())
	r = [int(i) for i in sys.stdin.readline().split()]
	es = [[] for i in range(n)]
	for i in range(m):
		line = [int(j) for j in sys.stdin.readline().split()]
		for u in line[1:]:
			es[u - 1].append(i)
	Adj = [[] for i in range(m)]
	for (u, v) in es:
		Adj[u].append(v)
		Adj[v].append(u)
	edges = dict()
	for (i, e) in enumerate(es):
		e.sort()
		if tuple(e) not in edges:
			edges[tuple(e)] = r[i]
		elif edges[tuple(e)] != r[i]:
			print('NO')
			return None
		else:
			pass
	cols = [None] * m
	for u in range(m):
		if cols[u] is None:
			if not bfs(Adj, edges, cols, u):
				print('NO')
				return None
			else:
				pass
	print('YES')

def bfs(Adj, edges, cols, u):
	nxts = deque([u])
	cols[u] = 0
	while nxts:
		v = nxts.popleft()
		for w in Adj[v]:
			ed = tuple(sorted([v, w]))
			if cols[w] is None:
				if edges[ed] == 1:
					cols[w] = cols[v]
				else:
					cols[w] = 1 - cols[v]
				nxts.append(w)
			elif edges[ed] == 1 and cols[w] != cols[v]:
				return False
			elif edges[ed] == 0 and cols[w] == cols[v]:
				return False
	return True

def __starting_point():
	solve()
__starting_point()


import sys
from math import inf
time = 0
cc = 0
l = {}
d = {}
f = {}
conn_comp = {}
on_stack = {}
stack = []
color = []

def tarjan(graph):
	global l
	global d
	global f
	global pi
	global stack
	global on_stack
	l = {key: inf for key in graph}
	d = {key: -1 for key in graph}
	f = {key: -1 for key in graph}
	conn_comp = {key: -1 for key in graph}
	on_stack = {key: False for key in graph}
	for i in graph.keys():
		if d[i] == -1:
			strongconnect(graph, i)

def strongconnect(graph, v):
	global time
	global cc
	stack.append(v)
	on_stack[v] = True
	time += 1
	d[v] = time
	for i in graph[v]:
		if d[i] == -1:
			strongconnect(graph, i)
			l[v] = min(l[v], l[i])
		if on_stack[i]:
			l[v] = min(l[v], d[i])
	if l[v] == d[v]:
		cc += 1
	w = stack.pop()
	while w != v:
		conn_comp[w] = cc
		on_stack[w] = False
		w = stack.pop()
	conn_comp[v] = cc
	on_stack[v] = False

def read():
	(n, m) = map(int, sys.stdin.readline().split())
	status = list(map(int, sys.stdin.readline().split()))
	doors_switch = [[] for i in range(n)]
	for i in range(m):
		temp = list(map(int, sys.stdin.readline().split()))
		for j in range(1, len(temp)):
			door = temp[j]
			doors_switch[door - 1].append(i)
	return (m, status, doors_switch)

def build_graph_scc():
	(m, status, doors_switch) = read()
	graph = {i: set() for i in range(2 * m)}
	for i in range(len(doors_switch)):
		(switch_1, switch_2) = tuple(doors_switch[i])
		if status[i]:
			graph[2 * switch_1].add(2 * switch_2)
			graph[2 * switch_2].add(2 * switch_1)
			graph[2 * switch_1 + 1].add(2 * switch_2 + 1)
			graph[2 * switch_2 + 1].add(2 * switch_1 + 1)
		else:
			graph[2 * switch_1].add(2 * switch_2 + 1)
			graph[2 * switch_2].add(2 * switch_1 + 1)
			graph[2 * switch_1 + 1].add(2 * switch_2)
			graph[2 * switch_2 + 1].add(2 * switch_1)
	return graph

def build_graph_bfs():
	(m, status, doors_switch) = read()
	g = [[] for i in range(m)]
	global color
	color = [-1] * m
	for i in range(len(status)):
		(switch_1, switch_2) = tuple(doors_switch[i])
		g[switch_1].append((switch_2, 1 - status[i]))
		g[switch_2].append((switch_1, 1 - status[i]))
	return g

def bfs_bipartite(graph, v):
	color[v] = 0
	q = [v]
	j = 0
	while j < len(q):
		v = q[j]
		for (w, st) in graph[v]:
			if color[w] == -1:
				color[w] = color[v] ^ st
				q.append(w)
			elif color[w] != color[v] ^ st:
				return False
		j += 1
	return True

def main():
	graph = build_graph_bfs()
	for i in range(len(graph)):
		if color[i] == -1 and (not bfs_bipartite(graph, i)):
			print('NO')
			return
	print('YES')
main()


from collections import deque

def bfs(adj, edge, col, u):
	nxt = deque([u])
	col[u] = 0
	while nxt:
		v = nxt.popleft()
		for w in adj[v]:
			a = [w, v]
			a.sort()
			a = tuple(a)
			if col[w] is None:
				col[w] = col[v] ^ edge[a]
				nxt.append(w)
			elif col[w] ^ col[v] != edge[a]:
				return -1
	return 0

def ri():
	return map(int, input().split())
(n, m) = ri()
e = [1 - i for i in ri()]
r = [[] for i in range(n)]
for i in range(m):
	s = list(ri())
	for j in range(1, len(s)):
		r[s[j] - 1].append(i)
edge = dict()
adj = [[] for i in range(m)]
for i in range(n):
	a = r[i]
	a.sort()
	a = tuple(a)
	if not a in edge:
		edge[a] = e[i]
		(a1, a2) = a
		adj[a1].append(a2)
		adj[a2].append(a1)
	elif edge[a] != e[i]:
		print('No')
		exit()
col = [None] * m
for u in range(m):
	if col[u] is None:
		if bfs(adj, edge, col, u):
			print('No')
			exit()
		else:
			pass
print('Yes')


from collections import defaultdict, deque
(n, m) = list(map(int, input().split()))
state = list(map(int, input().split()))
graph = defaultdict(list)
connected = [list() for _ in range(n + 1)]
for i in range(m):
	for j in list(map(int, input().split()))[1:]:
		connected[j].append(i)
for (index, i) in enumerate(connected[1:]):
	graph[i[0]].append((i[1], state[index]))
	graph[i[1]].append((i[0], state[index]))
switch_color = [False] * m
switch_visited = [False] * m
queue = deque([])
yes = True
for nodes in graph:
	if yes and (not switch_visited[nodes]):
		queue.append(nodes)
		while queue and yes:
			now = queue.popleft()
			switch_visited[now] = True
			for i in graph[now]:
				if not switch_visited[i[0]]:
					switch_visited[i[0]] = True
					queue.append(i[0])
					if i[1] == 1:
						switch_color[i[0]] = switch_color[now]
					else:
						switch_color[i[0]] = not switch_color[now]
				elif i[1] == 1 and switch_color[i[0]] != switch_color[now]:
					print('NO')
					yes = False
					break
				elif i[1] == 0 and switch_color[i[0]] == switch_color[now]:
					print('NO')
					yes = False
					break
if yes:
	print('YES')


import sys
(n, m) = map(int, input().split())
door = list(map(int, input().split()))
a = [[] for i in range(n + 1)]
e = [[] for i in range(m)]
color = [-1] * m
visited = [False] * m

def bfs(u, visited):
	color[u] = 0
	q = [u]
	h = 0
	visited[u] = True
	while h < len(q):
		u = q[h]
		h += 1
		for v in e[u]:
			if color[v[0]] == -1:
				color[v[0]] = color[u] ^ v[1]
				q.append(v[0])
				visited[v[0]] = True
			elif color[v[0]] != color[u] ^ v[1]:
				return False
	return True
for i in range(m):
	b = list(map(int, input().split()))
	for j in range(1, len(b)):
		k = b[j]
		a[k].append(i)
		if len(a[k]) == 2:
			e[a[k][0]].append((a[k][1], 1 - door[k - 1]))
			e[a[k][1]].append((a[k][0], 1 - door[k - 1]))
flag = True
for i in range(m):
	if color[i] == -1:
		if bfs(i, visited) == False:
			flag = False
			break
if flag:
	print('YES')
else:
	print('NO')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def find_SCC(graph):
	(SCC, S, P) = ([], [], [])
	depth = [0] * len(graph)
	stack = list(range(len(graph)))
	while stack:
		node = stack.pop()
		if node < 0:
			d = depth[~node] - 1
			if P[-1] > d:
				SCC.append(S[d:])
				del S[d:], P[-1]
				for node in SCC[-1]:
					depth[node] = -1
		elif depth[node] > 0:
			while P[-1] > depth[node]:
				P.pop()
		elif depth[node] == 0:
			S.append(node)
			P.append(len(S))
			depth[node] = len(S)
			stack.append(~node)
			stack += graph[node]
	return SCC[::-1]
for _ in range(int(input()) if not True else 1):
	(n, m) = map(int, input().split())
	r = list(map(int, input().split()))
	doors = [[] for __ in range(n + 1)]
	for i in range(m):
		a = list(map(int, input().split()))
		for j in range(1, len(a)):
			doors[a[j]] += [i + 1]
	graph = [[] for __ in range(2 * m + 1)]

	def add_edge(x, y):
		x2 = x - m if x > m else x + m
		y2 = y - m if y > m else y + m
		graph[x2] += [y]
		graph[y2] += [x]
	for i in range(1, n + 1):
		(x, y) = doors[i]
		x2 = x - m if x > m else x + m
		y2 = y - m if y > m else y + m
		if r[i - 1]:
			add_edge(x2, y)
			add_edge(x, y2)
		else:
			add_edge(x2, y2)
			add_edge(x, y)
	scc = find_SCC(graph)
	cx = [-1] * (2 * m + 1)
	pos = True
	for i in range(len(scc)):
		for j in scc[i]:
			cx[j] = i
	for i in range(1, m + 1):
		if cx[i] == cx[i + m]:
			pos = False
			break
	print('YES' if pos else 'NO')


import sys
import collections
(n, m) = map(int, input().split())
r = tuple(map(int, input().split()))
controls = [tuple(map(int, input().split()))[1:] for i in range(m)]

class DSU:

	def __init__(self):
		self.parent = None
		self.has_zero = False
		self.has_one = False
		self.size = 1
		self.doors = []

	def get_root(self):
		if self.parent is None:
			return self
		self.parent = self.parent.get_root()
		return self.parent

	def unite(self, s):
		r1 = self.get_root()
		r2 = s.get_root()
		if r1 is r2:
			return r1
		if r1.size < r2.size:
			(r1, r2) = (r2, r1)
		r2.parent = r1
		r1.size += r2.size
		r1.has_zero = r1.has_zero or r2.has_zero
		r1.has_one = r1.has_one or r2.has_one
		return r1
door_dsus = [[] for i in range(n)]
for doors in controls:
	n = DSU()
	for door in doors:
		n.doors.append(door - 1)
		door_dsus[door - 1].append(n)
		if r[door - 1]:
			n.has_one = True
		if not r[door - 1]:
			n.has_zero = True
for (door, is_open) in enumerate(r):
	(n1, n2) = door_dsus[door]
	if is_open:
		n1.unite(n2)
G = {}
for (door, is_open) in enumerate(r):
	if is_open:
		continue
	(n1, n2) = door_dsus[door]
	if n1.get_root() is n2.get_root():
		print('NO')
		sys.exit(0)
	G.setdefault(n1.get_root(), set()).add(n2.get_root())
	G.setdefault(n2.get_root(), set()).add(n1.get_root())
color = {}
for v in G.keys():
	if v in color:
		continue
	color[v] = False
	q = collections.deque([v])
	while q:
		v = q.popleft()
		c = color[v]
		for adj_v in G[v]:
			if adj_v in color:
				if color[adj_v] != (not c):
					print('NO')
					sys.exit(0)
			else:
				color[adj_v] = not c
				q.append(adj_v)
print('YES')


def _vertex(lit):
	if lit > 0:
		return 2 * (lit - 1)
	else:
		return 2 * (-lit - 1) + 1

def tarjan(graph):
	n = len(graph)
	dfs_num = [None] * n
	dfs_min = [n] * n
	waiting = []
	waits = [False] * n
	sccp = []
	dfs_time = 0
	times_seen = [-1] * n
	for start in range(n):
		if times_seen[start] == -1:
			times_seen[start] = 0
			to_visit = [start]
			while to_visit:
				node = to_visit[-1]
				if times_seen[node] == 0:
					dfs_num[node] = dfs_time
					dfs_min[node] = dfs_time
					dfs_time += 1
					waiting.append(node)
					waits[node] = True
				children = graph[node]
				if times_seen[node] == len(children):
					to_visit.pop()
					dfs_min[node] = dfs_num[node]
					for child in children:
						if waits[child] and dfs_min[child] < dfs_min[node]:
							dfs_min[node] = dfs_min[child]
					if dfs_min[node] == dfs_num[node]:
						component = []
						while True:
							u = waiting.pop()
							waits[u] = False
							component.append(u)
							if u == node:
								break
						sccp.append(component)
				else:
					child = children[times_seen[node]]
					times_seen[node] += 1
					if times_seen[child] == -1:
						times_seen[child] = 0
						to_visit.append(child)
	return sccp

def two_sat(formula):
	n = max((abs(clause[p]) for p in (0, 1) for clause in formula))
	graph = [[] for node in range(2 * n)]
	for (x, y) in formula:
		graph[_vertex(-x)].append(_vertex(y))
		graph[_vertex(-y)].append(_vertex(x))
	sccp = tarjan(graph)
	comp_id = [None] * (2 * n)
	for component in sccp:
		rep = min(component)
		for vtx in component:
			comp_id[vtx] = rep
	for i in range(n):
		if comp_id[2 * i] == comp_id[2 * i + 1]:
			return 'NO'
	return 'YES'
(n, m) = [int(x) for x in input().split()]
doors_status = [int(x) for x in input().split()]
switches = [list(map(int, input().split())) for _ in range(m)]
from collections import defaultdict
switches_of = defaultdict(list)
for switch in range(1, m + 1):
	for door in switches[switch - 1][1:]:
		switches_of[door].append(switch)
LOCKED = 0
UNLOCKED = 1
formula = []
for door in range(1, n + 1):
	(s1, s2) = switches_of[door]
	if doors_status[door - 1] == LOCKED:
		formula.append((s1, s2))
		formula.append((-s1, -s2))
	else:
		formula.append((s1, -s2))
		formula.append((-s1, s2))
print(two_sat(formula))


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
ais = [0] + list(map(int, input().split()))
doors = collections.defaultdict(list)
for i in range(m):
	dis = list(map(int, input().split()))[1:]
	for di in dis:
		doors[di].append(i + 1)
adj = collections.defaultdict(set)
for key in doors:
	(u, v) = doors[key]
	w = 1 - ais[key]
	adj[u].add((v, w))
	adj[v].add((u, w))
b = True
vis = {}
for cur in range(1, m + 1):
	if cur not in vis:
		q = collections.deque([cur])
		vis[cur] = 0
		while q:
			u = q.popleft()
			for (v, w) in adj[u]:
				if v not in vis:
					vis[v] = 1 - vis[u] if w == 1 else vis[u]
					q.append(v)
				elif v in vis:
					if w == 0:
						if vis[v] != vis[u]:
							b = False
					if w == 1:
						if vis[v] == vis[u]:
							b = False
print('YES' if b else 'NO')