← 返回题目列表

Codeforces · 825/E

E. 最小标签

中文机器翻译题面 查看原题

给定一个有 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