Switches and Lamps

Interview

Time limit2sMemory limit512 MB

Summary

Given N switches that each light some lamps and together cover every lamp, decide whether leaving out one switch still covers all lamps.

Level: Easy3 of 10
Topics: Implementation, Hash map, Greedy, Array
Solved: No attempts yet

Problem

Sangdo has N switches and M lamps. A switch can turn on a lamp. The number of lamps connected to a switch is 0 or more.

Initially, all lamps are off.

Pressing a switch turns on the lamps it is connected to. A switch cannot turn a lamp off. For example, if two switches are connected to one lamp, pressing either switch or pressing both switches leaves the lamp on.

Pressing all N switches turns on every lamp. Sangdo wonders whether pressing N-1 switches can also turn on every lamp.

Given the connections between the switches and the lamps, determine whether pressing N-1 switches can turn on every lamp.

Input

The first line contains the number of switches N and the number of lamps M. The next N lines describe the switches. The first integer on each line is the number of lamps connected to that switch, followed by the indices of the connected lamps separated by spaces.

Switches and lamps are numbered starting from 1.

Only inputs for which pressing all N switches turns on every lamp are given.

Output

Print 1 if pressing N-1 switches can turn on every lamp, and 0 otherwise.

Constraints

1 ≤ N, M ≤ 2,000

Examples3

Example 1
Input
```
4 5
3 1 3 5
1 2
3 3 4 5
1 1
```
Expected output
```
1
```
Example 2
Input
```
4 5
2 1 3
1 2
2 3 4
2 3 5
```
Expected output
```
0
```
Example 3
Input
```
10 1
1 1
0
0
0
0
0
0
0
0
1 1
```
Expected output
```
1
```