You have n gardens labeled from $1$ to n, and an array paths where paths[i] $= [x_i, y_i]$ represents a bidirectional path connecting garden $x_i$ and garden $y_i$.

You must plant one of $4$ flower types in each garden such that no two gardens connected by a path have the same flower type.

Return an array answer of length n, where answer[i] is the flower type planted in garden $i + 1$. The flower types are represented by the integers $1$, $2$, $3$, and $4$. It is guaranteed that a valid answer exists. If there are multiple valid answers, return any of them.

Constraints:

• $1 \leq$ n $\leq 10^4$

• $0 \leq$ paths.length $\leq 2 \times 10^4$

• paths[i].length $= 2$

• $1 \leq x_i, y_i \leq$ n

• $x_i \neq y_i$

• Every garden has at most $3$ paths connected to it.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.