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: competition

Starter code:

Solutions:
import sys
import collections

n, m = list(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")
        return

    G.setdefault(n1.get_root(), set()).add(n2.get_root())
    G.setdefault(n2.get_root(), set()).add(n1.get_root())

color = {}

for v in list(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")
                    return
            else:
                color[adj_v] = not c
                q.append(adj_v)

print("YES")


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)
            else:
                if 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 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 = [1 - 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:
                cols[w] = cols[v] ^ edges[ed]
                nxts.append(w)
            else:
                if cols[w] ^ cols[v] != edges[ed]:
                    return False

    return True

def __starting_point():
    solve()
__starting_point()

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 = [1 - 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:
                cols[w] = cols[v] ^ edges[ed]
                nxts.append(w)
            else:
                if cols[w] ^ cols[v] != edges[ed]:
                    return False

    return True

def __starting_point():
    solve()
__starting_point()

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
			else:
				if 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")

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)] #Each node connected to which 2 edges
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
# print(connected)
# print(graph)
queue = deque([])
yes = True
for nodes in graph:
    if yes and (not switch_visited[nodes]):
        # queue = deque([nodes])
        # yes = True
        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])
                else:
                    if (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")
# print(queue)
# print(switch_visited)
# print(switch_color)


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)] #Each node connected to which 2 edges
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
# print(connected)
# print(graph)
queue = deque([])
yes = True
for nodes in graph:
    if yes and (not switch_visited[nodes]):
        # queue = deque([nodes])
        # yes = True
        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])
                else:
                    if (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")

#!/usr/bin/env python3

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)
    #assignment = [None] * (2 * n)
    for component in sccp:
        rep = min(component)
        for vtx in component:
            comp_id[vtx] = rep
            #if assignment[vtx] is None:
            #    assignment[vtx] = True
            #    assignment[vtx ^ 1] = False
    for i in range(n):
        if comp_id[2 * i] == comp_id[2 * i + 1]:
            return "NO"
    return "YES"
    #return assignment[::2]


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))