Ghostbusters

A keyboard is a grid of $M$ rows and $N$ columns of buttons. Every row has one cable and every column has one cable. Pressing the button in row $i$ and column $j$ connects the cable of row $i$ with the cable of column $j$.

The firmware detects presses by sampling. It sends an electric signal into the cable of row 0. The signal spreads to every column cable joined to that row by a pressed button, then to every row cable joined to those columns by a pressed button, and so on. Every cable connected to the starting row through pressed buttons, directly or indirectly, receives the signal. The firmware records which columns received it, and repeats the whole process for every row.

A single press is easy to locate, because exactly one pair (row, column) makes contact. A keyboard also allows several buttons at once, and some combinations cannot be told apart. This effect is called ghosting. On a $2 \times 2$ keyboard, for example, every combination of three or four presses connects all four cables, so the recorded signals are identical.

Four examples of connected cables. Bold lines of the same colour mark cables joined by pressed buttons, drawn as red dots. The two sets on the right cannot be told apart, because they connect the same rows and the same columns.

Each button has its own probability of being pressed, and the buttons are pressed independently of each other. The probability of a set $S$ of pressed buttons is the product of $p_{ij}$ over the buttons in $S$, times the product of $1 - p_{ij}$ over the buttons outside $S$. Given the recorded signals, find the set of pressed buttons that could produce them and has the largest probability.

The first line has two integers $M$ and $N$, the number of rows and the number of columns. ($1 \le M, N \le 500$)

Each of the next $M$ lines has $N$ real numbers. The $j$-th number on the $i$-th line is the probability $p_{ij}$ that the button in row $i$ and column $j$ is pressed. ($0 < p_{ij} < 0.5$) Rows and columns are numbered from 0, so $0 \le i \le M-1$ and $0 \le j \le N-1$.

Each of the next $M$ lines starts with an integer $k$ ($0 \le k \le N$) followed by $k$ integers. Those $k$ integers are the columns that received the signal sent into row $i$.

The recorded signals always come from some real set of pressed buttons.

Print the set of pressed buttons with the largest probability. For each pressed button print one line with two integers $r$ and $c$, separated by a space: the row $r$ and the column $c$ of the button. Print the lines in increasing order of $r$, and in increasing order of $c$ among equal $r$.

If several sets reach the largest probability, print the lexicographically smallest one. Compare the sequences of (row, column) pairs sorted in the order above, and take the set whose first differing pair is smaller. If no button is pressed, print nothing.