New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Ninja And Flowers

Contributed by

Dhruv Sharma

Medium

0/80

10 mins

90 %

5 upvotes

Problem Statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

1 2 1 2

Explanation of sample input 1:

In the first test case, 
Gardens 1 and 2 have different types, and gardens 3 and 4 have different types. So, a possible answer to the question is when gardens 1 and 3 have the same type and gardens 2 and 4 have the same types of flowers. So print 1 2 1 2

Sample Input 2:

Sample Output 2:

1 2 3
1 2 1 2

Explanation of sample input 2:

In the first test case, 
Gardens 1 and 2 have different types, gardens 2 and 3 have different types, gardens 3 and 1 have different types. Hence, 1 2 3 is a valid answer. Other valid answers include 1 2 4, 4 2 1, 3 2 1. But 1 2 3 is lexicographically smallest, so you need to print 1 2 3

In the second test case, 
Gardens 1 and 2 have different types, gardens 2 and 3 have different types, gardens 3 and 4 have different types. So print 1 2 1 2.

Autocomplete

Console