如果序列 $a_1, a_2, \dots, a_n$ 包含从 $1$ 到 $n$ 的每个整数，则称其为一个排列。 如果对于图中的每一条有向边 $u \to v$，顶点 $u$ 在排列中都出现在 $v$ 之前，则称顶点序列 $a_1, a_2, \dots, a_n$ 为该有向图的一个拓扑排序。 如果存在某个 $m$，使得对于所有 $1 \le i < m$ 都有 $a_i = b_i$，且 $a_m < b_m$，则称排列 $a_1, a_2, \dots, a_n$ 在字典序上小于排列 $b_1, b_2, \dots, b_n$。

给定一个有向无环图，要求在图中添加至多 $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

5 3 2
1 4
4 2
1 3

样例输出 1

5 1 4 2 3
2
4 3
5 1

样例输入 2

2 2 20
1 2
1 2

样例输出 2

1 2
1
1 2