{"problem":{"name":"K. Topological Sort","description":{"content":"Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles. Your task is to find the lexicographically largest topological sort","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10110K"},"statements":[{"statement_type":"Markdown","content":"Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles.\n\nYour task is to find the lexicographically largest topological sort of the graph after removing a given list of edges.\n\nA topological sort of a directed graph is a sequence that contains all nodes from 1 to N in some order such that each node appears in the sequence before all nodes reachable from it.\n\nThe first line of input contains a single integer T, the number of test cases.\n\nThe first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively.\n\nEach of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.\n\nNo edge will appear in the list more than once.\n\nFor each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges.\n\n## Input\n\nThe first line of input contains a single integer T, the number of test cases.The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively.Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.No edge will appear in the list more than once.\n\n## Output\n\nFor each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $.  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, 2, \\dots, N\\} $ and initial edge set $ E_0 = \\{(u, v) \\mid 1 \\le u < v \\le N\\} $.  \nLet $ R \\subseteq E_0 $ be the set of $ M $ removed edges, where each $ (a, b) \\in R $ satisfies $ 1 \\le a < b \\le N $.  \nDefine the residual graph $ G' = (V, E') $ with $ E' = E_0 \\setminus R $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{number of test cases} $  \n2. For each test case:  \n   - $ 1 \\le N \\le 10^5 $  \n   - $ 0 \\le M \\le \\binom{N}{2} $  \n   - All edges in $ R $ are distinct and satisfy $ a < b $  \n\n**Objective**  \nFind the lexicographically largest topological ordering of $ G' $. That is, find a permutation $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_N) $ of $ \\{1, 2, \\dots, N\\} $ such that:  \n- For every $ (u, v) \\in E' $, $ \\pi^{-1}(u) < \\pi^{-1}(v) $,  \n- $ \\pi $ is lexicographically maximal among all valid topological orderings.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10110K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}