Assume that the number of colors $$$c$$$ is fixed. Let $$$mx[i][j]$$$ represent the length of the continuous path ending at node $$$i$$$ with color $$$j$$$. How do we construct $$$mx$$$?

Let's try some approaches. For the connected component formed by the first $$$k$$$ nodes, we can use color 1 for all of them. In this case, the $$$i$$$-th node's $$$mx$$$ array (for $$$1 \le i \le k$$$) would be:
$$$mx[i] = [0, \dots, 0, i]$$$.

For the $$$k$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes. Thus, the $$$k$$$-th node's $$$mx$$$ array would be:
$$$mx[k] = [0, \dots, 1, 0]$$$.

For the $$$(k+1)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes and color 1 to connect node $$$k$$$. In this case, the $$$(k+1)$$$-th node's $$$mx$$$ array would be:
$$$mx[k+1] = [0, \dots, 1, 1]$$$.

At this point, you might realize: The $$$i$$$-th node's $$$mx$$$ array is exactly the $$$(i-1)$$$ in base $$$k$$$ as a mask!

Claim $$$1$$$: for two indices $$$i$$$ and $$$j(i<j)$$$, $$$mx[i] /neq mx[j]$$$.

Proof $$$1$$$: if we use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$, $$$mx[i][k]+1=mx[j][k]$$$ must hold.

So we can assign values to each node's $$$mx$$$ array using a $$$k$$$-base mask from $$$0$$$ to $$$n-1$$$, which gives us a lower bound on the answer.

Claim $$$2$$$: we can always reach this lower bound.

Proof $$$2$$$: for two indices $$$i$$$ and $$$j(i<j)$$$, find $$$k$$$ such that $$$mx[i][k]<mx[j][k]$$$, then use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$.