Little W likes trees. One day, she constructed a tree with $n$ nodes in her dream and selected $m$ connected subgraphs to record. However, when she woke up from her dream, she found that she had forgotten the structure of the tree and the information about the connected subgraphs was also unclear. What she could be certain of is that the size of each of these connected subgraphs does not exceed $k$. Based on her memory, she wrote down the sets of vertices corresponding to these $m$ connected subgraphs. Can you tell her whether there exists a tree such that these $m$ sets of vertices are indeed connected subgraphs of this tree?

Input

The first line contains three positive integers $n, m, k$ ($1 \le n, m \le 10^4, 2 \le k \le 20$), representing the size of the original tree, the number of vertex sets, and the upper bound on the size of the vertex sets, respectively.

The next $m$ lines each contain several positive integers. The first positive integer is $s_i$ ($2 \le s_i \le k$), representing the size of the corresponding vertex set, followed by $s_i$ distinct positive integers representing the elements of this set.

Output

Output a single string. If such a tree exists, output YES. Otherwise, output NO (case-insensitive).

Examples

Input 1

5 3 3
3 1 2 3
3 2 3 4
3 5 2 1

Output 1

YES

Input 2

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

Output 2

NO