Problem A
Stable Perfect Matching

Two males displaying to a female masked bowerbird, Sericulus aureus, illustrated by John Gould (1804–1881).

We want to match up $n$ individuals into pairs taking into account their preferences. Each invididual has ranked all or some of the others in a preference list that describes which partner they would accept and prefer. In particular, if $u$ does not appear on $v$’s preference list and vice versa, the matching is unacceptable. We say that $u$ prefers $v$ to $w$ if $v$ comes before $w$ in the preference list of $u$. A matching is called a stable perfect matching if no two unmatched individuals $u$ and $v$ prefer each other to their respective partners.

To be more precise, in graph-theoretic terms the population makes up the vertex set $V$ of a simple and loopless graph $G$ with $m$ undirected edges $E$. Each vertex $u\in V$ has a total order of its neighbours, called a preference list. A perfect matching $S\subseteq E$ is a subset of $\frac12 n$ disjoint edges.¹ In other words, every vertex $v\in V$ appears in exactly one edge of the matching $S$. For an edge $uv\in S$ in a matching we say that $u$ and $v$ are matched and that $v$ is the partner of $u$ in $S$, and write $v=S(u)$. A pair $uv\in E-S$ of unmatched neighbouring vertices blocks² a matching $S$ if $u$ prefers $v$ to its partner $S(u)$, and $v$ prefers $u$ to its partner $S(v)$. A perfect matching is called stable if there is no blocking pair.

The task is to find a stable perfect matching, if it exists.

Constraints and Subtasks

You can assume that $n$ is even and $2\leq n\leq 200$. You can also assume that there are no isolated vertices, so $1\leq \frac12 n \leq m \leq \binom {n}{2} = 19\, 900$.

Note that subtask $1$ is small enough to admit an exhaustive search for $S$. Subtask $2$ is often called the Stable Marriage problem. Here, the population is divided into two parts of equal size, and the preference list of every individual includes all $\frac12n$ individuals from the other part (but none from its own.) In this case, is known that a stable perfect matching always exists. Subtask $4$, where all $\binom {n}{2}$ edges are present, is often called the Stable Roommates problem. Subtask $3$ includes $2$; subtask $5$ includes all other subtasks.

Input

On the first line, the integers $n$ and $m$.

Then follow $n$ lines. The $i$th of these lines describes the $i$th vertex of $G$ and its preferences. It contains $r\geq 2$ space-separated tokens made up of at most $12$ English upper- and lowercase letters and digits. The first token is the name of the $i$th vertex; the remaining $r-1$ tokens give the preferences of this vertex in order, beginning with the most preferred neighbour. All vertex names are different.

For bipartite instances, the lines are ordered such that the first $\frac12 n$ lines of input describe the vertices of the first part.

Output

If there is no stable perfect matching, print a single hyphen “-”. Otherwise print a stable perfect matching on exactly $\frac12 n$ lines, one line per edge. The order of the lines, and the order of the vertex pair on each line, are not important. If there is more than one stable perfect matching, any will do.

2 1
Ken Barbie
Barbie Ken

Barbie Ken

8 16
Charlotte Bingley Darcy Collins Wickham
Elizabeth Wickham Darcy Bingley Collins
Jane Bingley Wickham Darcy Collins
Lydia Bingley Wickham Darcy Collins
Bingley Jane Elizabeth Lydia Charlotte
Collins Jane Elizabeth Lydia Charlotte
Darcy Elizabeth Jane Charlotte Lydia
Wickham Lydia Jane Elizabeth Charlotte

Charlotte Collins
Darcy Elizabeth
Bingley Jane
Lydia Wickham

6 8
Chandler Monica Rachel Phoebe
Joey Rachel Phoebe Monica
Ross Rachel Phoebe
Monica Chandler Joey
Phoebe Joey Ross Chandler
Rachel Ross Joey Chandler

Chandler Monica
Joey Phoebe
Rachel Ross

4 3
A a
B a b
a B A
b B

-

4 3
A a
B a b
a A B
b B

A a
B b

4 6
1 3 2 4
2 1 3 4
3 2 1 4
4 1 2 3

-

4 6
A B C D
B A C D
C A B D
D C A B

A B
C D

6 15
1 4 6 2 5 3
2 6 3 5 1 4
3 4 5 1 6 2
4 2 6 5 1 3
5 4 2 3 6 1
6 5 1 4 2 3

1 6
2 3
4 5

6 15
1 2 6 4 3 5
2 3 5 1 6 4
3 1 6 2 5 4
4 5 2 3 6 1
5 6 1 3 4 2
6 4 2 5 1 3

-

10 45
1 8 2 9 3 6 4 5 7 10
2 4 3 8 9 5 1 10 6 7
3 5 6 8 2 1 7 10 4 9
4 10 7 9 3 1 6 2 5 8
5 7 4 10 8 2 6 3 1 9
6 2 8 7 3 4 10 1 5 9
7 2 1 8 3 5 10 4 6 9
8 10 4 2 5 6 7 1 3 9
9 6 7 2 5 10 3 4 8 1
10 3 1 6 5 2 9 8 4 7

1 7
2 8
3 6
4 9
10 5