给定一个有 n 个顶点和 m 个边的有向无环图。任何一对顶点之间不存在自环或重边。图可以断开。
您应该通过以下方式为所有顶点分配标签:
- 标签形成长度为 n 的有效排列 - 一个整数序列,使得从 1 到 n 的每个整数在其中恰好出现一次。
- 如果存在从顶点 v 到顶点 u 的边,则 labelv 应小于 labelu。
- 排列应该是所有合适排列中字典顺序最小的。
找到满足所有条件的标签序列。
输入
第一行包含两个整数 n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105)。
接下来的 m 行包含两个整数 v 和 u (1 ≤ v, u ≤ n, v ≠ u) — 图的边。边是有向的,图不包含环或多边。
输出
打印 n 个数字 — 按字典顺序排列的顶点标签的最小正确排列。
示例
输入 #1
3 3 1 2 1 3 3 2
输出 #1
1 3 2
输入 #2
4 5 3 1 4 1 2 3 3 4 2 4
输出 #2
4 1 2 3
输入 #3
5 4 3 1 2 1 2 3 4 5
输出 #3
3 1 2 4 5