Steam coupling

A graph is termed bipartite if its vertex set (V) can be divided into two disjoint subsets, (A) and (B), such that every edge in the graph connects a vertex from (A) to a vertex from (B). A matching in a graph is a subset (S) of the edge set (E) where no two edges share a common vertex. In other words, for any edges (e_1 = (u_1, v_1)) and (e_2 = (u_2, v_2)) in (S), it must hold that (u_1 $\ne$ u_2), (u_1 $\ne$ v_2), (v_1 $\ne$ u_2), and (v_1 $\ne$ v_2).

Your task is to determine the maximum matching in the given bipartite graph. A matching is considered maximum if it contains the largest possible number of edges.

Input

The first line of the input contains two integers, (N) and (M) ((1 $\le$ N, M $\le$ 250)), representing the number of vertices in sets (A) and (B), respectively. The following (N) lines describe the edges of the graph. The ((i+1))-th line provides a list of vertices from set (B) that are connected to the (i)-th vertex of set (A). Each list concludes with the number (0). The vertices in sets (A) and (B) are independently numbered starting from (1).

Output

The first line of the output should contain a single integer (L), which is the number of edges in the maximum matching. Each of the following (L) lines should describe one edge of the matching, consisting of two integers (u_i) and (v_i), where (u_i) is the vertex number in set (A) and (v_i) is the vertex number in set (B).

Examples