We will call nodes which will have blue-eyed logicians on them black nodes, and the other nodes will be called white nodes. Notice that every black node has exactly one black neighbour and that it is also that node's neighbour. Thus, the black nodes come in pairs as the endpoints of certain edges.

For the first subtask, one should notice that the nodes in a cycle should alternate between two black nodes and two white nodes, so the solution exists only when ~n~ is divisible by ~4~ and the answer is then ~n/2~.

The second subtask can be solved by trying out all possibilities for the black nodes with time complexity ~\mathcal O(2^n n)~.

For the remaining subtasks, one should notice that the graph contains exactly one cycle, where from each node of the cycle, a tree might hang off rooted at that node. Using a DFS we can find that cycle and then remove one of the edges of the cycle. One of the ends we will call the root, and the other one will be the special node. After removing the edge, the remaining graph is a tree, which we will root in the mentioned root node.

The task will be solved with dynamic programming on the obtained tree. We will fix one of the possibilities for the choice of colour of the root and the special node (~4~ possibilities), and add this information to the state of our dp. The state will have the current node which determines the current subtree and an additional ~4~ flags: the state is ~DP[x][me][up][rt][sp]~ which denotes the least number of black nodes in the subtree of node ~x~ if the colour of node ~x~ is written in the flag ~me~, the colour of the parent of ~x~ is ~up~, the colour of the root is ~rt~, and the colour of the special node is ~sp~. In the state, we assume that the parent of ~x~ has already taken care of having a black neighbour, so that we are left to determine the colours of the nodes in the subtree of ~x~.

The transition is as follows. First, we determine the cases in which the flags in the state don't match up (so the answer is immediately -1 for this state). This happens when:

• ~x~ is the root, and ~me \ne rt~.
• ~x~ is the special node, and ~me \ne sp~.
• ~x~ is the special node, and ~rt~ and ~up~ are black - then ~x~ is covered by two black neighbours.

Then we figure out if the current node ~x~ already has a black neighbour. This is true either when ~up~ is black, or if ~x~ is the root and ~sp~ is black, or if ~x~ is the special node and ~rt~ is black. If ~x~ happens to already be covered, none of his children are allowed to be black, so the solution is given by summing the expression ~DP[v][\text{white}][me][rt][sp]~ over all children ~v~ of ~x~. If ~x~ is not covered, we have to choose one of the children which will be black, and the rest of them will be white. We do this by calculating the same sum as above, except changing the ~me~ flag for one of the children to 'black'. We try this for each child and determine which one gives the least result.