现在给出一张含有 n 个点的有向无环图,我们称这张图是“有序图”当且仅当这个图满足以下条件: 1. 存在一个 1-n 数字的全排列 p ,并令 i 号结点的权值为 p[i] 。 2. 如果图中存在 u 号结点到 v 号结点的一条边,则 u 号结点的权值要小于 v 号结点的权值。 显然可能有多个序列满足条件,请你找出字典序最小的全排列 p ,使得这个图成为有序图。 数据范围:
输入描述:
第一行包含两个正整数n,m,分别表示图上结点是数量和有向边的数量。 接下来m行每行有两个正整数u,v,表示存在一条从u结点到v结点的有向边。


输出描述:
输出一个字典序最小的,1-n的全排列,使得这张图是有序图,元素中间使用空格隔开。
示例1

输入

3 3
1 2
1 3
3 2

输出

1 3 2
加载中...