Alice and Bob's Paper Game

Alice and Bob play a game with paper slips. Initially, each has an empty paper. In total there are $n$ rounds. In each round $i$ both players will write one positive integer in the range $[1, m]$ on their paper. Alice writes her number first and Bob writes later after seeing Alice’s paper. However, there are restrictions. In round $i$, Alice must choose her number $a_i$ from a given set $S_i\subseteq\{1,2,\dots,m\}$ and Bob must choose his number $b_i$ from a given set $T_i\subseteq\{1,2,\dots,m\}$. It is guaranteed that (1\le |S_i|,|T_i|\le 2). Moreover, Bob must guarantee that his $n$ numbers are pairwise distinct.

Alice loves similarity so she wants as many indices with $a_i=b_i$ as possible, while Bob (subject to his distinctness constraint) wants to minimize the number of indices with $a_i=b_i$. In other words, if we define [ X=|{ i:; 1\le i\le n \text{ and } a_i=b_i}|, ] then under optimal play we have:

• Alice tries to maximize (X),
• Bob, while ensuring that (b_1,\dots,b_n) are distinct, tries to minimize (X).

Furthermore, note that Bob writes his numbers after seeing Alice’s choices. Thus, in rounds where his set $T_i$ has exactly one element (a forced round), he has no choice; and naturally, if the forced number is available in $S_i$, Alice will choose it to force a match. In rounds where $|T_i|=2$, Bob will try to avoid a match by picking an element different from $a_i$, but his options may be limited by the overall distinctness requirement. In particular, if $S_i\cap T_i\neq \emptyset$, then Alice can choose a number from the intersection. In such rounds Bob can choose the other number as a safe option unless conflicts force him to choose $a_i$ (thereby increasing (X)). On the other hand, if $S_i\cap T_i=\emptyset$, Bob cannot cause a match in that round.

Your task is as follows. First, determine if Bob can guarantee that the $n$ numbers he writes are pairwise distinct. If not, output -1. Otherwise, assuming both players play optimally, compute the final value of (X).

All formulas must be formatted in (\LaTeX).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1\le n\le 50,\; 1\le m\le 50)\), representing the number of rounds and the upper bound.

The following \(n\) lines describe the sets \(S_i\). Each line begins with an integer \(k\) (\(1\le k\le 2\)) followed by \(k\) distinct integers in the range \([1,m]\) that form \(S_i\).

The next \(n\) lines describe the sets \(T_i\). Each line begins with an integer \(k\) (\(1\le k\le 2\)) followed by \(k\) distinct integers in the range \([1,m]\) that form \(T_i\).

outputFormat

If Bob cannot guarantee that his \(n\) numbers are pairwise distinct, output -1. Otherwise, output a single integer, the value of \(X\) (the number of rounds in which \(a_i=b_i\)) when both players play optimally.

sample

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

1