Hotel Management

Interview

Time limit2sMemory limit512 MB

Summary

Each room belongs to exactly two switches; find whether pressing some subset of switches turns every room's lock state to open.

Level: Medium6 of 10
Topics: Graph, DFS, Union-find, Bit manipulation
Solved: No attempts yet

Problem

The Gusagwa Hotel has N rooms in total and M switches that control the lock states of the rooms. Every room is connected to two switches.

Given the initial lock states of the rooms, you want to use the switches to open every room. Pressing a switch flips the states of the rooms connected to it. For example, if rooms 1, 2, and 3 are open, closed, and open, and all of them are connected to switch 1, then pressing this switch changes the room states to closed, open, and closed.

Determine whether every room can be opened using the switches.

Input

The first line contains the number of rooms N (2 ≤ N ≤ 100,000) and the number of switches M (2 ≤ M ≤ 100,000). The second line contains the initial lock states of the rooms in order from room 1. 0 means closed and 1 means open.

Each of the next M lines describes the rooms connected to one switch. The description of each switch starts with a single integer K followed by K room numbers separated by spaces. Each room number is an integer between 1 and N inclusive, and the given switch descriptions satisfy the conditions of the problem.

Output

Print 1 if every room can be opened, and 0 otherwise.

Examples3

Example 1
Input
```
3 3
1 0 1
2 1 3
2 1 2
2 2 3
```
Expected output
```
0
```
Example 2
Input
```
3 3
1 0 1
3 1 2 3
1 2
2 1 3
```
Expected output
```
1
```
Example 3
Input
```
3 3
1 0 1
3 1 2 3
2 1 2
1 3
```
Expected output
```
0
```