Problem B
The Colonization of El-gă-rizm
The mythical planet, El-gă-rizm, comprises $m$ islands surrounded by water. There are $n$ different natural resources to be found at various locations on the islands. Interestingly, each of the $n$ natural resources is present on exactly two islands; thus there are $2n$ total occurrences of resources on El-gă-rizm.
Both the Zax and Xaz beings simultaneously attempt to colonize the islands of El-gă-rizm. The Zax and Xaz mistrust each other. They will share the planet but refuse to share any individual island or any resources on an island. Thus each island is populated by only Zax or Xaz, never both. Collectively, the Zax have access to all natural resources on islands they populate. The Xaz also have access to all natural resources on islands that they populate. In order to survive on El-gă-rizm, a being needs access to all $n$ natural resources.
Can the Zax and Xaz coexist on El-gă-rizm?
Input
The first line contains the positive integers $m$ and $n$, separated by a space, representing the number of islands and the number of different natural resources, respectively. Following that are $m$ lines. The $i$-th such line specifies the natural resources present on the $i$-th island, as a sequence of integers, separated by spaces. The different natural resources are represented by the integers $1, 2, 3, \ldots , n$. The last value on each of the $m$ lines is always $0$. The value $0$ does not represent a natural resource; it only indicates that there are no more subsequent values on that line.
You may assume that $m$ and $n$ are each no greater than $1\, 000\, 000$.
Output
The output should be a single line consisting of the string YES if the Zax and Xaz can coexist on El-gă-rizm, or the string NO otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 8 0 2 4 0 1 8 0 8 5 0 4 3 7 0 5 2 6 0 1 6 0 7 3 0 |
YES |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 6 4 3 0 6 0 1 2 6 5 4 0 2 5 1 3 0 |
NO |
