Without loss of generality, assume \(C_0=0\). For convenience, for \(2 \leq i \leq N\) where \(C_i=0\), we reset \(C_i=2K+1\).

Consider the graph remaining after removing vertex \(1\), and we can separate the problem for each connected component.

We solve the problem for one connected component \(X\). Assume that starting from this connected component plus slime \(1\), we can leave only slime \(1\), and derive necessary conditions. s We reformulate the problem setting as follows:

• First, perform the operation of adding \(2K+1\) to \(C_i\) a many times as desired. Then, eliminate slimes. However, the condition for choosing \(u\) and \(v\) is \(C_u+1 \leq C_v \leq C_u+K\).

There must exist at least one \(i\) with \(1 \leq C_i \leq K\), so let \(r\) be an \(i\) that achieves the maximum value of \(C_i\) among them (if there is a tie, take any \(r\)). Here, for any connected component \(Y\) consisting of \(i\) satisfying \(C_i > K\), the following condition should hold:

• In \(Y\), there exists \(i\) satisfying \(K+1 \leq C_i \leq C_r+K\).

Organizing this condition in terms of the input \(C_i\), we can summarize it as follows:

• There exists a vertex \(r\) satisfying the following conditions:
• \(1 \leq C_r \leq K\)
• For each connected component \(Z\) of the graph after removing \(r\) from \(X\), one of the following holds:
  • \(C_i \leq K\) for all \(i\) contained in \(Z\).
  • There exists \(i\) contained in \(Z\) satisfying \(K+1 \leq C_i \leq C_r+K\).

This is a necessary condition, and we now prove that it is also sufficient.

Take an \(r\) satisfying the above condition, and for each connected component \(Z\), consider performing the following operations:

• Call slimes satisfying \(C_i\leq K\) type-P, slimes satisfying \(K+1 \leq C_i \leq C_r+K\) type-Q, and slimes satisfying \(C_r+K+1 \leq C_i\) type-R. Since the above condition is satisfied, it is guaranteed that we do not have “\(0\) slimes of type-Q and \(1\) or more slimes of type-R.” When type-R slimes exist, slimes other than type-R also exist, and necessarily there exist adjacent slimes \(u\) and \(v\) where \(u\) is type-R and \(v\) is type-P or Q. Here, perform the operation on \(u\) and \(v\). Depending on the values of \(C_u\) and \(C_v\), which eats which changes, but in any case, type-Q slimes will not disappear. Therefore, by repeating this operation, we can reach a state where there are \(0\) type-R slimes. After that, consider appropriately performing operations as much as possible. If only type-P survives, the processing for \(Z\) is complete. If only type-Q survives, let \(r\) eat all surviving slimes. In the end, only type-P remains in \(Z\).

After these operations, only \(i\) satisfying \(1 \leq C_i \leq K\) remain in \(X\). Therefore, we can let slime \(1\) eat all of these, leaving only slime \(1\).

This proves the sufficiency of the aforementioned condition.

Now, consider checking this condition. This can be done by decomposing the graph into articulation points and then performing tree DP. By computing “the minimum value of \(C_i\) satisfying \(C_i \geq K+1\)” for each subtree in the DP, we can check the condition.

The time complexity is \(O(N+M)\).

Sample solution (C++)