You are given a connected, undirected, unweighted graph. You need to assign one of the two colors Red or Blue to every edge of the graph in such a way that, for each node .
of a node is the number of adjacent edges to that node which are colored Red.
of a node is the number of adjacent edges to that node which are colored Blue.
The first line contains one integer - the number of test cases. First line of each testcase contains two integers , - the number of vertices and the number of edges in the graph respectively. Each of the next lines contain two integers and describing an undirected edge in the graph.
Sum of over all testcases doesn’t exceed and sum of over all testcases also doesn’t exceed .
It is guaranteed that the graph is connected, it has no self-loop and there is at most one edge between every pair of vertices.
If it is not possible to find such a coloring, print . Otherwise print one such coloring of the edges in the order given. If there exists more than one coloring you can print any one. You should print a string containing only and to denote the coloring.
2 6 5 1 2 1 3 2 4 2 5 5 6 3 3 1 2 2 3 1 3