Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Ninja And Flowers

Moderate
0/80
Average time to solve is 10m
7 upvotes
Asked in companies
SamsungWiproSigmoid

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 )
Constraints:
1 <= T <= 10
1 <= N <= 10^3
0 <= X <= 10^3
1 <= Y1, Y2 <= N

Time limit: 1 sec 
Sample Input 1:
1
4 2
1 2
3 4
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:
2
3 3
1 2
2 3
3 1
4 3
1 2
2 3
3 4
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.
Full screen
Console