Problem A
Holiday Scheduling

You were asked to help a hospital in Basel to schedule the shifts of their doctors during the public holidays of next year. However, there are a few problems. First, some doctors have availability constraints: they are available to work only during some of the public holidays. Second, according to the hospital policy, each doctor cannot work more than a certain number of public holidays.

Given a list of holidays, doctors, and availability constraints, can you say if it is possible to find a schedule where at least one doctor works on each holiday, while respecting all doctors’ constraints and the hospital policy?

Input

The input starts with three natural numbers $h, d$, and $c$:

• $h$ is the number of public holidays. Holidays are numbered from $0$ to $h-1$.

• $d$ is the number of doctors.

• $c$ is the maximum number of holidays that the hospital policy allows each doctor to work.

The next $d$ lines describe the holidays in which each doctor is available. Line $i$ starts with a natural number $r$, representing the number of holidays the $i$-th doctor is available (i.e., holidays when this doctor can work). This is followed by $r$ natural numbers $m_1, \ldots , m_ r$, where $m_ j$ (for some $1 \leq j \leq r$) indicates that this doctor can work on public holiday $m_ j$.

Output

If there is an assignment of doctors to holidays satisfying all constraints (availability constraints and hospital policy), your program should output “yes”. Otherwise, it should output “no”.

Limits

• $0 \le h \le 1\, 500$

• $0 \le d \le 500$

• $0 \le c \le 10$, $c \le h$

• $r \le h$

• $m_ j < h$

6 2 3
4 0 1 3 4
4 1 2 4 5

yes

6 3 4
4 0 1 3 4
0
4 1 2 4 5

yes

9 4 2
5 0 1 3 4 8
5 0 4 6 2 8
3 1 5 7
4 8 3 1 5

no