{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"For 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"You are given a directed graph with N nodes (labeled 1 to N) and an edge from every smaller node to every larger node (so u → v for all u < v). This graph has no cycles.\n\nYou are also given M edges to remove. After removing those edges, find the lexicographically largest possible topological order of the remaining graph.\n\nPrint the topological order as N space-separated integers.","has_page_source":false}