n flowerbeds numbered 1 to n. Some pairs of beds are joined by paths: paths[i] = [x, y] is a path between beds x and y. No bed has more than three paths.
Each bed is planted in one of four colors: 1, 2, 3 or 4. Two beds joined by a path must get different colors.
Return an array colors of length n, where colors[i] is the color of bed i + 1. Many colorings may work; return the lexicographically smallest one: bed 1 gets the smallest possible color, then bed 2 given that, and so on.n=4, paths=[[1, 2], [2, 3], [3, 1], [3, 4]] → [1, 2, 3, 1]
Bed 1 gets color 1. Bed 2 borders bed 1, so it gets 2. Bed 3 borders beds 1 and 2, so it gets 3. Bed 4 borders only bed 3, so color 1 works.
n=3, paths=[] → [1, 1, 1]
There are no paths, so every bed can take color 1.
n=4, paths=[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] → [1, 2, 3, 4]
Every bed borders all the others, so all four colors are needed.
n=4, paths=[[1, 2], [2, 3], [3, 1], [3, 4]]
[1, 2, 3, 1]
Run checks the first 3 tests in your browser. Submit checks all 32 tests on the server, hidden ones included.