本文共 3117 字，大约阅读时间需要 10 分钟。

Problem Description

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 ≤ 105,

2 ≤ m ≤ 105) — the number of rooms and the number of switches.

Next line contains n space-separated integers r1, r2, …, rn

(0 ≤ ri ≤ 1) which tell the status of room doors. The i-th room is

locked if ri = 0, otherwise it is unlocked.

The i-th of next m lines contains an integer xi (0 ≤ xi ≤ n) followed

by xi 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.

Example

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

因为一个门只由两个开关控制，

当开关个数为m时，开一个2*m大的数组father[]，前m个father[i]代表第i个开关按下的状态，后m个father[i]为第i-n个开关没按下的状态；当最后结果father[i]与father[i+n]连通的时候（状态一致），结果矛盾，n个门将不会同时全开，因为一个开关不可能同时两种状态。

判断是否连通要用到 并查集。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;vector
        
          a[100010]; //相当于二维数组，但更好操作int father[200120],door[100010];int find_father(int x){ if(father[x]==x) return x; return father[x]=find_father(father[x]);}void merge(int x,int y){ int fx=find_father(x); int fy=find_father(y); if(fx!=fy){ father[fx]=fy; }}int main(){ int m,n,flag=1; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>door[i];//门的状态 a[i].clear(); } int k;int x; for(int i=1;i<=2*m;i++) father[i]=i;//初始化，自己是自己的祖先 for(int i=1;i<=m;i++){ cin>>k; for(int j=1;j<=k;j++){ cin>>x; a[x].push_back(i);//把控制同一个门的开关放到一起 } } for(int i=1;i<=n;++i){ if(door[i]){ //如果门开着，两个开关连通 merge(a[i][0],a[i][1]); merge(a[i][0]+m,a[i][1]+m); } else{ //否则，两个开关必须状态不同 merge(a[i][0],a[i][1]+m); merge(a[i][0]+m,a[i][1]); } } for(int i=1;i<=m;i++){ if(find_father(i)==find_father(i+m)){ flag=0; break; } } if(flag) cout<<"YES\n"; else cout<<"NO\n"; return 0;}
        
       
      
     
    
   

转载地址：http://djmdi.baihongyu.com/