25975번 - 스택 재정렬 스페셜 저지

N 개의 스택에 1부터 N까지의 번호가 붙어있다. 스택의 초기 상태와 목표 상태가 주어졌을 때 다음과 같은 규칙을 적용하여 초기 상태를 목표 상태로 바꾸려고 한다. 규칙을 적용하는 횟수는 170,000 번 이하여야 하지만 그 횟수가 최소가 될 필요는 없다.

• N 개의 스택 중 원소가 있는 스택을 하나 골라서 가장 위에 있는 원소를 빼고, 스택 하나를 골라서 그 원소를 가장 위에 넣는다. 원소를 빼는 스택과 넣는 스택은 같을 수 있다.

입력의 첫 번째 줄에는 스택의 개수 N과 모든 스택의 원소의 개수의 합 M이 공백으로 구분되어 주어진다.

그다음 N 줄에는 스택의 초기 상태가 주어진다.

1 ≤ i ≤ N인 정수 i에 대하여 입력의 i + 1 번째 줄에는 i 번 스택의 초기 상태를 나타내는 p_i + 1 개의 정수가 공백으로 구분되어 주어진다. 입력의 i + 1 번째 줄의 첫 번째 수는 p_i로, i 번 스택의 초기 상태에서의 원소의 개수를 나타낸다. i + 1 번째 줄의 나머지 수는 i 번 스택의 초기 상태에서의 가장 아래에 있는 원소부터 가장 위에 있는 원소까지를 순서대로 나타낸다.

그다음 N 줄에는 스택의 목표 상태가 주어진다.

1 ≤ i ≤ N인 정수 i에 대하여 입력의 i + N + 1 번째 줄에는 i 번 스택의 목표 상태를 나타내는 q_i + 1 개의 정수가 공백으로 구분되어 주어진다. 입력의 i + N + 1 번째 줄의 첫 번째 수는 q_i로, i 번 스택의 목표 상태에서의 원소의 개수를 나타낸다. i + N + 1 번째 줄의 나머지 수는 i 번 스택의 목표 상태에서의 가장 아래에 있는 원소부터 가장 위에 있는 원소까지를 순서대로 나타낸다.

규칙을 0 번 이상 적용하여 스택의 초기 상태로부터 목표 상태로 바꾸는 것이 가능한 입력만 주어진다. 또, 입력 조건을 만족하는 모든 입력에 대하여 규칙을 170,000 번 이하로 적용하여 스택의 초기 상태로부터 목표 상태로 바꾸는 것이 가능함을 증명할 수 있다.

출력의 첫 번째 줄에는 스택을 초기 상태와 목표 상태로 바꾸기 위해 규칙을 적용하는 횟수 X를 출력한다.

그다음 X 줄에는 규칙을 적용하는 과정을 출력한다.

1 ≤ i ≤ X인 정수 i에 대하여 출력의 i + 1 번째 줄에는 규칙을 i 번째 적용할 때 원소를 빼는 스택의 번호 d_i와 원소를 넣는 스택의 번호 e_i를 공백으로 구분하여 출력한다.

• 3 ≤ N ≤ 10,000
• 0 ≤ M ≤ 10,000
• 0 ≤ p_i ≤ M
• 0 ≤ q_i ≤ M
• p₁ + p₂ + … + p_N = q₁ + q₂ + … + q_N = M
• 스택의 모든 원소는 -1,000,000,000 이상 1,000,000,000 이하의 정수이다.
• 0 ≤ X ≤ 170,000
• 1 ≤ d_i ≤ N
• 1 ≤ e_i ≤ N