Ninja And Flowers

Contributed by
Dhruv Sharma
Medium
0/80
10 mins
90 %

Problem Statement

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.
``````
Autocomplete
Console