Hospital

문제

You are writing a personnel management tool for a large hospital. One of the problems is managing the vacation plans of employees.

There are two types of nurses working in the hospital: staff nurses continuously take care of the patients and special nurses fill special positions like “surgical nurse” or “nurse supervisor”. When a staff nurse goes on vacation, nothing critical happens, because other nurses will do her work. But when special nurse goes on vacation, she must be substituted. For every special nurse there is a list of nurses, who can substitute her. If the substituting nurse is a special nurse too, then some third nurse must substitute her as well, and so on. Sometimes it is impossible for special nurse to go on vacation, because there is no sequence of substitutions, after that all special nurse positions are filled.

Consider the following example. There are seven nurses in a hospital. Alice, Bob, Clara, Dona and Emma are special nurses, Fiona and Gloria are staff nurses. They can substitute each other according to the following scheme (arrow from A to B means A can substitute B):

[이미지 1]

In this example, Dona and Emma cannot go on vacation, because if one of them does, another cannot fill both positions. Alice, Bob and Clara can go on vacation, but Bob and Clara cannot do it at the same time, because Gloria cannot substitute them both simultaneously.

Your task is to find all nurses who cannot go on vacation, and all pairs of nurses, such that both can go on vacation, but not in the same time.

입력

The first line of the input file contains two integer numbers n and k — the total number of nurses and number of special nurses. Nurses 1 ... k are special nurses, and nurses k + 1 ... n are staff nurses (1 ≤ k < n ≤ 1000). Next k lines contain the lists of possible substitutions. The first number in (i+1)-th line is d_i — the number of nurses, who can substitute i-th nurse. Following d_i numbers in the same line are the indices of substituting nurses. The total length of all lists does not exceed 10 000.

출력

First output the number of nurses who cannot go on vacation. Then output their indices.

After that, output the number of pairs of nurses, such that both can go on vacation, but not at the same time. Finally, if the number of such pairs is not greater then 10 000, output all these pairs (pairs (A, B) and (B, A) are considered equal).