뒤섞인 스택

$n$장의 카드에는 1부터 $n$까지 번호가 붙어 있고, 이 카드들은 $k$개의 스택 $S_1, S_2, \ldots, S_k$에 나뉘어 놓여 있다. 각 스택에는 용량 제한이 있다. $i$번째 스택 $S_i$에는 최대 $C_i$장까지 쌓을 수 있다. 카드를 다루는 방법은 스택의 맨 위 카드를 꺼내 다른 스택의 맨 위에 옮기는 것뿐이다. 이때 옮기는 스택의 용량을 넘을 수 없다.

이런 이동을 반복해서, 번호가 작은 쪽의 스택 몇 개(0개 이상)는 용량을 꽉 채우고, 그 다음 스택은 꽉 채우지 않으며(비어 있어도 된다), 그 뒤의 스택은 모두 비도록 카드를 재배치하려고 한다. 또한 $S_1$을 맨 아래, $S_k$를 맨 위로 두고 모든 스택을 이어 쌓았을 때, 카드는 아래에서 위로 1부터 $n$까지 작은 순서로 정렬되어 있어야 한다.

$n \le \left(\sum_{i=1}^k C_i\right) - \max_{1 \le i \le k} C_i$임이 보장된다.

$n = 6$, $k = 3$인 경우를 보자. 용량은 $C_1 = 4$, $C_2 = C_3 = 3$이고, 초기 상태는 $S_1 = [2, 3, 0, 0]$(아래에서 위 순서, $0$은 빈 칸), $S_2 = [4, 1, 6]$, $S_3 = [5, 0, 0]$이다. 이때 원하는 최종 상태는 $S_1 = [1, 2, 3, 4]$, $S_2 = [5, 6, 0]$, $S_3 = [0, 0, 0]$이다.

첫 줄에는 카드의 개수 $n$과 스택의 개수 $k$가 공백으로 구분되어 주어진다. 이어지는 $k$개의 줄은 각 스택의 초기 상태를 나타낸다. $i$번째 줄은 $S_i$에 대한 정보이며, 공백으로 구분된 $C_i + 1$개의 정수를 담고 있다. 첫 번째 정수는 $S_i$의 용량 $C_i$이고, 나머지는 $S_i$에 있는 카드 번호를 아래에서 위 순서로 적은 것이다. $S_i$의 카드가 $C_i$장보다 적으면(비어 있을 수도 있다) 줄의 마지막 몇 개 정수는 0이다.

스택을 원하는 최종 상태로 만드는 이동 순서를 출력한다. 각 이동마다 카드를 꺼내는 스택의 번호와 카드를 옮길 스택의 번호를 공백으로 구분하여 한 줄에 출력한다. 스택 번호는 1부터 $k$까지이며, 옮길 스택은 꺼낼 스택과 달라야 한다. 이동 횟수는 $10^5$를 넘을 수 없다. 이동을 모두 출력한 뒤에는 "0 0"(따옴표는 제외)이라는 줄을 출력한다. 가능한 해가 여러 개라면 그중 어느 것을 출력해도 된다.

• $1 \le n \le 100$
• $3 \le k \le 100$
• $1 \le C_i \le n$

이 문제는 앞의 문제 설명에서 든 예시이다. 샘플 출력은 스택을 원하는 최종 상태로 만드는 14번의 이동을 보여준다.