Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Ninja And Flowers
MEDIUM
10 mins
5 upvotes
Graph
Greedy
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Graph
-
-
Greedy
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Dynamic Programming
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
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.

Ninja And Flowers

Contributed by
Dhruv Sharma
Medium
yellow-spark
0/80
Avg time to solve 10 mins
Success Rate 90 %
Share
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, Constraints, Images )
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.
Reset Code
Full screen
Auto
copy-code
Console