Description
You have n gardens and paths between them. Plant flowers (1-4) such that no two connected gardens have the same flower. Return flower assignments.
Examples
Input:
n = 3, paths = [[1,2],[2,3],[3,1]]Output:
[1,2,3]Explanation:
Each garden different from neighbors.
Input:
n = 3, paths = [[1]]Output:
[1]Explanation:
Minimal case with a single path.
Input:
n = 4, paths = [[1,2],[2,3]]Output:
[1,1,2,1]Explanation:
Gardens 1 and 2 are connected, so they get different flower types (1 and 1). Gardens 2 and 3 are connected, so garden 3 gets a different type from garden 2 (type 2). Garden 4 has no connections, so it can use any type (type 1). This demonstrates a linear chain with one isolated garden.
Constraints
- •
1 ≤ n ≤ 10⁴