printРабочее место участника


1917. Commissions

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

There are some commissions in the parliament. Each deputy may be a member of some commissions, in particular neither of them. The chairman of the every commission is its member. Nobody of deputies can be chairman of more than one commission simultaneously.
In the result of regular election the membership of parliament is not changed. The commissions were reformed. It’s interesting, that all old chairmen became chairmen again, but maybe of other commissions.
Write the program, which determines the chairmen of commissions based on the staff of commissions of old and new parliaments.
The first line of the input file contains two integers `N` and `K` (`2\ ≤\ N\ ≤\ 100`, `1\ ≤\ K\ ≤\ N/2`), separated by space, where `N` is the quantity of deputies in parliament and `K` is the quantity of commissions. The following `K` lines describe the staff of old commissions. `i`-th line contains an integer `P_i` (`1\ ≤\ P_i\ ≤\ N`), which is equal to the amount of members of `i`-th commission, and then `P_i` numbers of them. All integers are separated by spaces. The next `K` lines describe new commissions similarly.
Write into the output file `K` lines; `i`-th line has to contain two integers, where the first one is the number of new `i`-th commission's chairman, and the second one is the number of commission in old parliament, where he was chairman. If there are some such variants of chairs distribution, you should output one of them.

Sample Input

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

Sample Output

5 3
4 2
2 1