Hospital

You are building a vacation-management system for a large hospital. Its nurses come in two kinds.

• A general nurse cares for inpatients. If a general nurse goes on vacation another nurse can simply absorb the work, so there is no problem.
• A special nurse holds a dedicated post such as "surgical nurse" or "head nurse", and may go on vacation only if there is a substitute to cover the post.

Every special nurse has a list of nurses who can cover their post. When a special nurse goes on vacation, one nurse from that list takes over the post. If the nurse who took over is itself another special nurse, then that nurse's own post must in turn be covered by someone else. The vacation is possible only if this chain of substitutions eventually ends with a general nurse filling a post. A nurse can cover at most one post at a time, and a nurse who is on vacation cannot cover any post. If no valid chain of substitutions exists, that special nurse cannot go on vacation.

For example, suppose there are $7$ nurses where $1$–$5$ are special and $6$–$7$ are general, and the nurses who can cover each special nurse are as follows: nurse $1$ by $6$ or $7$, nurse $2$ by $7$, nurse $3$ by $2$ or $7$, nurse $4$ by $5$, nurse $5$ by $4$. Here nurses $4$ and $5$ can only cover each other, so if one takes a vacation the other cannot cover both posts at once; neither can ever go on vacation. Nurses $1$, $2$, and $3$ can each go on vacation. However, nurses $2$ and $3$ both ultimately depend on nurse $7$, who cannot cover two posts at once, so $2$ and $3$ cannot be on vacation at the same time.

Given the substitution information of all nurses, write a program that finds the nurses who can never take a vacation, and every pair of nurses who can each take a vacation individually but not at the same time.

The first line contains the total number of nurses $n$ and the number of special nurses $k$. Nurses $1$ through $k$ are special and nurses $k+1$ through $n$ are general. ($1 \le k < n \le 1000$)

Each of the next $k$ lines describes who can cover a special nurse; the $i$-th of these lines is for special nurse $i$. Its first number is the count $d_i$ of nurses who can cover nurse $i$, followed by those $d_i$ nurse numbers. The total length of all lists does not exceed $10\,000$.

On the first line, print the number of nurses who can never take a vacation. On the second line, print their numbers in ascending order separated by spaces (print an empty line if there are none).

On the third line, print the number of pairs of nurses who can each take a vacation individually but cannot be on vacation at the same time. The pairs $(A, B)$ and $(B, A)$ count as the same pair. If this number is at most $10\,000$, then on each following line print one such pair as its two nurse numbers with $A < B$, listing the pairs sorted in ascending order by the first number and then by the second.