Let's construct a graph where the nodes are the fields of the board, and the edges are obtained by connecting two nodes of each arrow that is not in the last column, using a directed edge. Since each node has a degree of at most ~1~, the obtained graph consists of two different types of components:

• Directed tree
• Cycle with "branches" leading to it

Each path from the first column to the last column is actually a path from a tree node to the root of that same tree. Let's mark the nodes in the first column as "special". Now the task is actually to color the ~K~ nodes of the tree so that each path from a special node to the root contains exactly one colored node. Let's apply a trick: we can add an auxiliary node to the graph and an edge from each root to that auxiliary node. Now we have exactly ~1~ tree in the graph and its solution is checked using dynamic programming.

Let's calculate the value of function ~f(x, i, k)~ that returns whether we can color all subtrees of node ~x~ from its ~i^\text{th}~ child onwards. The crucial part is to determine how many nodes we will color in the ~i^\text{th}~ subtree. If we color exactly ~y~ nodes, the solution exists if both values of ~f(x, i+1, k-y)~ and ~f(child[x][i], 0, y)~ are equal to ~1~. In the end, we make sure that we can arbitrarily color the nodes in the components that lead to cycles. If we iterate over all possible ~y~, the complexity of this algorithm is ~\mathcal O(NMK^2)~.

In order to speed up the solution, we can use bitmasks. Let's denote the bitmask that contains bit ~f(x, i+1, k)~ in the ~k^\text{th}~ position with ~F[x][i]~. Additionally, we denote with ~R[x][i]~ that same mask with the first ~50~ bits in reverse (the ~0^\text{th}~ element of ~F~ is the ~50^\text{th}~ of ~R~). Now ~f(x, i, k) = (R[x][i] \gg (50-k)) \mathbin\& F[child[x][i]]~. We leave it as an exercise for the reader the proof of the correctness of this optimization that enables the speed-up of the aforementioned dynamic programming approach to ~\mathcal O(NMK)~.