AdditionalFile5557.zip

#5557. 「POI2026 R1」Hanoj

标签: 传统 | 时间限制: 6000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Hanoj

Bajtyna 在一个可疑网站上买了一款玩具，本以为会收到经典的「汉诺塔」，结果收到的是「哈诺伊塔」（Wieże Hanoj）。

哈诺伊塔由 $m$ 个柱子组成，上面总共有 $n$ 个大小各不相同的圆盘，编号从 $1$ 到 $n$。

在游戏的任意时刻，每个柱子上的圆盘从顶部到底部必须严格递增排序（即越靠近底部编号越大）。

允许的唯一操作只有一种：

把任意柱子最顶上的圆盘取下，放到任意柱子的最底部。

Bajtyna 想知道：最少需要多少次这样的操作，才能把所有圆盘都移动到同一个柱子上。

请你帮她求出这个最小操作次数，并输出一种合法的操作方案。

输入格式

第一行两个整数 $n, m$ $(2 \leq m \leq n \leq 10^6)$，分别表示圆盘数量和柱子数量。柱子编号从 $1$ 到 $m$。

接下来 $m$ 行，第 $i$ 行描述第 $i$ 个柱子的初始状态：

首先一个整数 $k_i$ 表示该柱子上的圆盘数量，接着 $k_i$ 个整数 $v_{i,1}, v_{i,2}, \dots, v_{i,k_i}$，表示从顶部到底部的圆盘编号，且满足 $1 \leq v_{i,1} < v_{i,2} < \cdots < v_{i,k_i} \leq n$。

所有圆盘编号互不相同，且恰好覆盖 $1$ 到 $n$（即 $\sum k_i = n$）。

输出格式

如果无法把所有圆盘聚集到同一个柱子，只输出一行 -1。否则第一行输出一个整数 $h$，表示最少的操作次数。 接下来 $h$ 行，每行两个整数 $a_i\ b_i$ $(1 \leq a_i, b_i \leq m)$， 表示把柱子 $a_i$ 最顶上的圆盘移动到柱子 $b_i$ 的最底部。如果有多种方案，输出任意一种即可。

只要你输出的第一行（即操作次数 $h$）正确，即使后面的移动序列缺失或错误，你仍能得到该测试点 $50\%$ 的分数。

样例 1

输入

3 3
1 2
2 1 3
0

输出

3
2 3
1 3
2 3

初始状态：

• 柱子 $1$：顶部 $2$
• 柱子 $2$：顶部 $1 \to 3$
• 柱子 $3$：空

操作过程：

1. 把柱子 $2$ 最上面的 $1$ 放到柱子 $3$ 底部 $\to$ 柱子 $3$：$1$
2. 把柱子 $1$ 最上面的 $2$ 放到柱子 $3$ 底部 $\to$ 柱子 $3$：$1 \to 2$
3. 把柱子 $2$ 最上面的 $3$ 放到柱子 $3$ 底部 $\to$ 柱子 $3$：$1 \to 2 \to 3$

整个过程始终保持每个柱子柱严格递增，最终所有圆盘都在柱子 $3$ 上。

样例 2

输入

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

输出

-1

不可能达成目标，故输出 -1。

附加样例

1. $10$ 个圆盘，$2$ 个柱子，其中一个柱子为空
2. $1000$ 个圆盘，$3$ 个柱子，其中一个为空，另外两个分别放偶数编号和奇数编号的圆盘
3. $n = m = 10^6$，每个柱子上恰好一个圆盘

数据范围与提示

详细子任务附加限制及分值如下表所示。