题目描述

在教授 Optimizorov 面前有一个复杂的优化问题。

在某个项目中，需要完成 N 个任务，编号为 1 到 N，而这些任务的执行顺序由一个有向无环图决定。更准确地说，这些任务编号位于一个有向无环图的顶点上；如果编号为 u 和 v 的任务之间有一条从 u 指向 v 的有向边，那么这表示任务 u 必须在任务 v 之前完成。

我们称任务 u 是任务 v 的前驱，而任务 v 是任务 u 的后继。因此，只有当某个任务的所有前驱都已经完成时，这个任务才可以开始执行。

我们不讨论这个优化问题本身，也不讨论教授那套非常厉害的求解算法的具体内容，只说明一点：这套算法要求对图的顶点重新编号（仍然使用 1 到 N），并且重新编号必须满足一种非常特殊的规则。下面给出定义。

定义： 给定两个数列 F = (f_1, f_2, ..., f_p) 和 Q = (q_1, q_2, ..., q_r)。如果 p = 0 或 r = 0，则相应数列为空。

我们称数列 F 的字典序小于数列 Q，当且仅当满足以下两种情况之一：

• 存在某个 i，使得对于所有 1 ≤ j < i 都有 f_j = q_j，并且 f_i < q_i；
• 或者 p < r，且对于所有 1 ≤ j ≤ p 都有 f_j = q_j。

显然，字典序最小的是空数列。

现在设想，在重新编号以后，对图中每个顶点都关联一个由其所有后继的新编号组成的数列，并按降序排列。我们把这个数列称为该顶点的后继序列。

新的编号必须满足：

• 一个顶点的新编号小于另一个顶点的新编号，当且仅当它的后继序列按字典序小于另一个顶点的后继序列；
• 如果两个顶点拥有完全相同的后继集合，那么原编号较小的顶点必须获得较小的新编号。

请你帮助教授，编写程序 renum，完成这种重新编号。

输入格式

第一行输入两个正整数 N 和 M，分别表示图中的顶点数和边数。

接下来 M 行，每行输入两个正整数，表示一条有向边的起点和终点。

输出格式

输出 N 行。

每行输出两个正整数，中间用一个空格分隔：

• 第一个数是顶点的原编号；
• 第二个数是顶点的新编号。

输出行必须按照原编号升序排列。

说明

如果你稍微认真思考一下，就会发现本题的解是唯一的。

数据范围

• 2 ≤ N ≤ 100000
• 2 ≤ M ≤ 1000000

在 20% 的测试中：

• N ≤ 200
• M ≤ 200

样例输入

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

样例输出

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

样例解释

原题在样例解释中给出了两幅图：

重新编号前的图；

重新编号后的图。

解释如下：

新编号为 1、2、3 的顶点，其后继序列均为空，因此它们获得了最前面的三个编号；这三者之间具体谁拿到更小的新编号，则由原编号大小决定。

新编号为 4、5、6 的顶点，其后继序列分别为：

• {2}
• {2, 1}
• {3, 2}

这些后继序列的字典序关系决定了它们的相对新编号。