Bajtysia 和 Bajteusz 是著名的旅行家，他们几乎已经游历了拜托西亚（Byteotia）的每一个角落。这个国度由 $n$ 个城市组成，编号为 $1$ 到 $n$，城市之间由单向道路网络连接。然而，传统的旅行方式已经让他们感到厌倦——凡是能到达的地方，他们都已经去过了。

最近，Bajtysia 获得了一个古老的魔法神器——道路名录（Wykaz Dróg）。它允许在城市之间创建新的单向道路。然而，这里有一个限制：名录的魔法非常任性，它只允许在当前无法通过已有道路网络连通的两个城市之间创建道路（即不存在从第一个城市到第二个城市的道路序列；但是，可以存在从第二个城市到第一个城市的道路序列）。如果尝试在已经连通的两个城市之间创建道路，将会导致失败并摧毁该名录。

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

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

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1500$，$0 \le m \le n(n-1)$），分别表示拜托西亚的城市数量和单向道路数量。

接下来的 $m$ 行包含对道路的描述。其中的第 $i$ 行（对于 $1 \le i \le m$）包含两个整数 $a_i, b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示存在一条从城市 $a_i$ 到城市 $b_i$ 的单向道路。描述的单向道路不会重复。

输出格式

输出的第一行应包含一个非负整数 $k$，表示最多可以创建的单向道路数量，使得每条新创建的道路连接的两个城市在当时都是无法连通的。

接下来的 $k$ 行应当描述需要依次创建的道路。其中的第 $i$ 行（对于 $1 \le i \le 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

输出样例 1

3
4 1
6 4
7 6

输入样例 2

3 0

输出样例 2

5
3 1
3 2
2 1
2 3
1 2

说明

样例解释：

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

由于无法从城市 4 到达城市 1，因此我们可以添加这样一条道路，得到如下所示的道路网络：

在添加了从城市 6 到城市 4 以及从城市 7 到城市 6 的道路后，我们得到了一个在任意一对城市之间都可以互相到达的网络。此时无法再添加更多的边。

样例测试：

样例 0a、0b 即为上述的两个样例。此外：

• 0c: $n = 50, m = 50, a_i = i$，而对于每个 $i \ne 25$ 且 $i \ne 50$ 有 $b_i = i + 1$，且 $b_{25} = 1, b_{50} = 26$。
• 0d: $n = 500, m = 0$。

子任务

测试点分为以下子任务。每个子任务的测试由一个或多个独立的测试点组组成。

如果你的输出中只有第一行（即 $k$）是正确的，你的程序将获得该测试点 50% 的分数。你不需要输出接下来的几行来获得这部分分数。