{"problem":{"name":"E. Minimal Labels","description":{"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. You should assign labels to ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF825E"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint _n_ numbers — lexicographically smallest correct permutation of labels of vertices.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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] 个数字 —— 顶点标签的字典序最小的合法排列。\n\n## Input\n\n第一行包含两个整数 #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]) —— 图的边。边是有向的，图中不包含环或多重边。\n\n## Output\n\n请输出 #cf_span[n] 个数字 —— 顶点标签的字典序最小的合法排列。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF825E","tags":["data structures","dfs and similar","graphs","greedy"],"sample_group":[["3 3\n1 2\n1 3\n3 2","1 3 2"],["4 5\n3 1\n4 1\n2 3\n3 4\n2 4","4 1 2 3"],["5 4\n3 1\n2 1\n2 3\n4 5","3 1 2 4 5"]],"created_at":"2026-03-03 11:00:39"}}