题目描述

序列 $a_{1}, a_{2}, \ldots, a_{n}$ 被称为一个排列，如果它包含从 $1$ 到 $n$ 的每一个整数。

如果顶点的排列 $a_{1}, a_{2}, \ldots, a_{n}$ 是一个有向图的拓扑序，那么对于每一条从 $u$ 到 $v$ 的有向边，顶点 $u$ 在这个排列中出现在 $v$ 之前。

排列 $a_{1}, a_{2}, \ldots, a_{n}$ 在字典序上小于排列 $b_{1}, b_{2}, \ldots, b_{n}$，如果存在某个 $m$ 使得对于每一个 $1 \le i < m$，都有 $a_{i} = b_{i}$，并且 $a_{m} < b_{m}$。

给定一个有向无环图，最多添加 $k$ 条有向边，使得结果图仍然没有环，并且图的字典序最小的拓扑序尽可能大。

输入格式

输入文件的第一行包含三个整数 $n, m$ 和 $k$ —— 原始图中的顶点数和有向边数，以及允许添加的有向边数 $(1 \le n \le 100 000; 0 \le m, k \le 100 000)$。

接下来的 $m$ 行中的每一行包含两个整数 $u_{i}, v_{i}$，描述从 $u_{i}$ 到 $v_{i}$ 的有向边 $(1 \le u_{i}, v_{i} \le n)$。

图中没有环。

输出格式

输出文件的第一行应包含 $n$ 个整数 —— 修改后的图的字典序最小的拓扑序。第二行应包含一个整数 $x (0 \le x \le k)$ —— 添加的有向边的数量。接下来的 $x$ 行应包含添加的有向边的描述，格式与输入文件相同。

输入输出样例 #1

输入 #1

5 3 2
1 4
4 2
1 3

输出 #1

5 1 4 2 3
2
4 3
5 1

输入输出样例 #2

输入 #2

2 2 20
1 2
1 2

输出 #2

1 2
1
1 2