Strings and Graphs

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Consider a sequence of positive integers A = (A_{1}, A_{2}, ... , A_{N}), and another sequence B = (B_{1}, B_{2}, ... , B_{M}). We say that B is a subsequence of A, if B can be written as (A_{i1}, A_{i2}, ... , A_{iM}), where 1 ≤ i_{1} < i_{2} ... < i_{M} ≤ N. If B is a subsequence of A, there could be multiple ways to write it in such a manner, and among all those ways, we choose the way which minimizes i_{M}. We call this minimized i_{M} to be f(B). Note that in the definition of f(B), we are assuming that A is a constant. Also, when B is the empty sequence, it is considered to be a subsequence of A, and f(B) would then be 0.
Now, given A, we will construct a graph G which has N + 1 nodes and labeled directed edges. The nodes are {V_{0}, V_{1}, ..., V_{N}}. If there are two subsequences of A: C_{1} and C_{2}, such that C_{2} is obtained by appending the integer b at the end of C_{1}, and f(C_{1}) ≠ f(C_{2}), then the edge ( V_{f(C1)}, b, V_{f(C2)} ) is added to the graph G if it is not already present in the graph. (Note that even if an edge with a different label is already present, this edge is added. Just that there will not be multiple edges from one vertex to another with the same label). The edge (V_{i}, b, V_{j}) means that it is a directed edge from V_{i} to V_{j}, and it has the label b.
Chef constructed this graph, but then lost the sequence A, as well as all the labels on the graph. So all he has left is a directed graph (with possibly multiple edges from one vertex to another), and now he wants to find the sequence A. Since there could be many such sequences which fit the graph, he wants to find the lexicographically smallest such sequence. Help Chef in finding this.
Input
 The first line contains a single integer, T, which is the number of testcases. The description of each testcase follows.
 The first line of each testcase contains two integers, N and M. This means that the input graph has vertices {V_{0}, V_{1}, ..., V_{N}} and M directed multiedges.
 The ith of the next M lines contains two integers, x_{i} and y_{i}, which denote that there is a directed edge from V_{xi} to V_{yi}.
Output
For each testcase, output a single line which contains N positive integers which denote the lexicographically smallest sequence which can lead to the construction of the inputted graph. Or, if such a sequence does not exist, output 1.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, M ≤ 10^{5}
 0 ≤ x_{i}, y_{i} ≤ N
Subtasks
 Subtask 1 (30 points) : N, M ≤ 10^{3}
 Subtask 2 (70 points) : Original constraints
Example
Input: 2 5 11 0 1 0 2 0 5 2 3 2 5 1 3 1 5 1 2 3 4 3 5 4 5 3 4 0 3 2 3 1 2 0 1 Output: 1 2 1 1 3 1
Explanation
Testcase 1:
Let us consider the sequence A = (1, 2, 1, 1, 3).
f(empty string) = 0, and f( (1) ) = 1. (1) can be obtained by appending 1 to the empty string. Hence there should be an edge from V_{0} to V_{1} with the label 1.
Similarly, f( (1, 2, 1) ) = 3 and f( (1, 2, 1, 3) ) = 5. Hence there should be an edge from V_{3} to V_{5} with label 3.
By looking at all such possible pairs of valid subsequences, we can see that the edges obtained from this A exactly match the edges given in the input graph. And this is the lexicographically smallest such sequence. Hence the answer is this sequence.
Testcase 2:
There is no sequence which leads to the construction of this graph. Hence the answer is 1.
Author:  admin3 
Editorial  https://discuss.codechef.com/problems/STRINGRA 
Tags  adhoc, admin3, aug17, easymedium, greedy, sorting 
Date Added:  2082017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions