Look at a leaf in the graph. If the piece on that vertex shows white, that vertex must be chosen before the adjacent vertex. On the other hand, if that piece shows black, that vertex must be chosen after the adjacent vertex.

Using this observation, we can solve the decision problem. Since the case with one vertex is trivial, we assume there are two or more vertices. Choose any leaf. If it must be chosen after the adjacent vertex, the problem can be solved by solving the decision problem for the tree obtained by removing that vertex. On the other hand, if it must be chosen before the adjacent vertex, the problem can be solved by flipping the piece on the adjacent vertex and then solving the decision problem for the tree obtained by removing that vertex. In short, the decision problem can be solved recursively on the number of edges.

• Actually, the answer is yes if and only if the number of pieces showing white is odd.

Next, let us consider how to find the lexicographically smallest sequence of operations. Again, for each edge, we can recursively determine which of the endpoints should be chosen first. Additionally, it can also be seen that any sequence of operations following these orders is feasible. Thus, the problem can be rephrased into finding the lexicographically smallest topological sort of a DAG. This can be solved by successively removing the vertex with the smallest index whose in-degree is \(0\).