AdditionalFile5630.zip

#5630. 「POI2026 R2」Wykaz dróg

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – II etap Wykaz dróg

Bajtysia 和 Bajteusz 是著名的旅行家，他们几乎已经游遍了 Bajtocja 的每一个角落。这片土地由 $n$ 个城市组成，编号从 $1$ 到 $n$，城市之间由单向道路网连接。然而，传统的旅行方式已经开始让他们感到厌倦——凡是能去的地方，他们都已经去过了。

最近，Bajtysia 获得了一件古老的魔法神器——道路清单（Wykaz Dróg）。它允许在城市之间创建新的单向道路。不过，这里有一个限制。清单的魔力反复无常，只有在两个城市之间目前无法通过现有道路网通行时，才允许在它们之间创建道路（即不存在从第一个城市通往第二个城市的道路路径；但可能存在从第二个城市返回第一个城市的道路路径）。如果尝试在两个已经可以通行的城市之间创建道路，操作将会失败并损毁清单。

对于 Bajtysia 和 Bajteusz 来说，这是一个极好的挑战！他们立刻决定，想要变出尽可能多的新道路。

不幸的是，Bajtysia 和 Bajteusz 正忙于规划下一次远征，无法亲自解决这个问题。请帮他们规划应该依次创建哪些道路，以使道路的总数达到最大。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 1500, 0 \leq m \leq n(n-1))$，分别表示 Bajtocja 的城市数量和单向道路数量。

接下来的 $m$ 行包含道路的描述。其中第 $i$ 行（对于 $1 \leq i \leq m$）包含两个整数 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示存在一条从城市 $a_{i}$ 到城市 $b_{i}$ 的单向道路。描述的单向道路不会重复。

输出格式

第一行输出一个非负整数 $k$，表示可以创建的单向道路的最大数量，使得每条新道路连接的一对城市之间当前都无法通行。

接下来的 $k$ 行应描述按顺序创建的道路。其中第 $i$ 行（对于 $1 \leq i \leq k$）应包含两个整数 $c_{i}, d_{i}$，表示第 $i$ 条创建的道路。在创建这条道路的时刻，利用现有的道路（包括初始道路和之前已创建的道路）应无法从城市 $c_{i}$ 前往城市 $d_{i}$。

如果存在多种可能的解，输出其中任意一个即可。

样例 1

输入

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

输出

3
4 1
6 4
7 6

在第一个样例中，初始存在的道路网如下图所示。

由于无法从城市 $4$ 前往城市 $1$，因此可以添加这样一条道路，得到如下图所示的道路网。

在添加了从城市 $6$ 到城市 $4$ 以及从城市 $7$ 到城市 $6$ 的道路后，我们将得到一个任意两点间都可达的网络。无法再添加更多的边了。

样例 2

输入

3 0

输出

5
3 1
3 2
2 1
2 3
1 2

附加样例

1. $n=50, m=50$。对于每个 $i \neq 25$ 且 $i \neq 50$，有 $a_{i}=i, b_{i}=i+1$；且 $b_{25}=1, b_{50}=26$。
2. $n=500, m=0$。

数据范围与提示

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

如果你只输出了正确的第一行（即最大数量 $k$），你的程序将获得该测试点 $50\%$ 的分数。为了获得这部分分数，你不需要输出后续的 $k$ 行。