Ninja And Flowers

Ninja has ‘N’ gardens labeled from [1, N] under his supervision. He created an array that stores bidirectional paths between I1 and I2, where I1 and I2 are gardens stored at the position I in the array. In each garden, he wants to plant 4 types of flowers.

You need to choose a flower type for each garden such that any two gardens connected by a path, have different types of flowers.

Note:

1. All gardens have at most three paths coming into or leaving the garden. 
2. There can be more than one possible answer to this question. You need to print the smallest valid answer when all possible answers are sorted in lexicographical order.

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘X’, denoting the number of gardens Ninja has and the number of queries regarding the paths between the gardens.

The next ‘X’ lines of each test contain an array of ‘X’ pairs where each pair denotes a bidirectional path between the two values of the pair.

Output Format:

For each test case, you need to return an array of integers denoting the flower type of each garden.

Print the output of each test case in a separate line.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^3
0 <= X <= 10^3
1 <= Y1, Y2 <= N

Time limit: 1 sec