{"raw_statement":[{"iden":"statement","content":"You are given a directed acyclic graph with _n_ vertices and _m_ edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.\n\nYou should assign labels to all vertices in such a way that:\n\n*   Labels form a valid permutation of length _n_ — an integer sequence such that each integer from 1 to _n_ appears exactly once in it.\n*   If there exists an edge from vertex _v_ to vertex _u_ then _label__v_ should be smaller than _label__u_.\n*   Permutation should be lexicographically smallest among all suitable.\n\nFind such sequence of labels to satisfy all the conditions."},{"iden":"input","content":"The first line contains two integer numbers _n_, _m_ (2 ≤ _n_ ≤ 105, 1 ≤ _m_ ≤ 105).\n\nNext _m_ lines contain two integer numbers _v_ and _u_ (1 ≤ _v_, _u_ ≤ _n_, _v_ ≠ _u_) — edges of the graph. Edges are directed, graph doesn't contain loops or multiple edges."},{"iden":"output","content":"Print _n_ numbers — lexicographically smallest correct permutation of labels of vertices."},{"iden":"examples","content":"Input\n\n3 3\n1 2\n1 3\n3 2\n\nOutput\n\n1 3 2 \n\nInput\n\n4 5\n3 1\n4 1\n2 3\n3 4\n2 4\n\nOutput\n\n4 1 2 3 \n\nInput\n\n5 4\n3 1\n2 1\n2 3\n4 5\n\nOutput\n\n3 1 2 4 5"}],"translated_statement":[{"iden":"statement","content":"给定一个有 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向无环图。图中不存在自环，任意两个顶点之间也不存在多条边。图可以是不连通的。\n\n你需要为所有顶点分配标签，使得：\n\n找到满足所有条件的标签序列。\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105])。\n\n接下来 #cf_span[m] 行每行包含两个整数 #cf_span[v] 和 #cf_span[u] (#cf_span[1 ≤ v, u ≤ n, v ≠ u]) —— 图的边。边是有向的，图中不包含环或多重边。\n\n请输出 #cf_span[n] 个数字 —— 顶点标签的字典序最小的合法排列。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n ≤ 105, 1 ≤ m ≤ 105])。接下来 #cf_span[m] 行每行包含两个整数 #cf_span[v] 和 #cf_span[u] (#cf_span[1 ≤ v, u ≤ n, v ≠ u]) —— 图的边。边是有向的，图中不包含环或多重边。"},{"iden":"output","content":"请输出 #cf_span[n] 个数字 —— 顶点标签的字典序最小的合法排列。"},{"iden":"examples","content":"输入\n3 3\n1 2\n1 3\n3 2\n输出\n1 3 2 \n\n输入\n4 5\n3 1\n4 1\n2 3\n3 4\n2 4\n输出\n4 1 2 3 \n\n输入\n5 4\n3 1\n2 1\n2 3\n4 5\n输出\n3 1 2 4 5 "}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a directed acyclic graph (DAG), where:  \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of vertices,  \n- $ E \\subseteq V \\times V $ is the set of directed edges, with $ |E| = m $,  \n- No self-loops or multiple edges: $ (v, u) \\in E \\Rightarrow v \\ne u $, and no duplicate edges.  \n\nLet $ \\ell: V \\to \\{1, 2, \\dots, n\\} $ be a bijection (labeling) assigning distinct integer labels from $ 1 $ to $ n $ to the vertices.\n\n**Constraints**  \nFor every directed edge $ (v, u) \\in E $, it must hold that:  \n$$\n\\ell(v) < \\ell(u)\n$$\n\n**Objective**  \nFind the lexicographically smallest such labeling $ \\ell $ satisfying all edge constraints.","simple_statement":null,"has_page_source":false}