In essence, we have a directed graph where each vertex has exactly one outgoing arc. We are asked to redirect some of the arcs so that each vertex is in a "pair" and we are asked to do it with the minimum number of redirects. This type of graph, called a "functional graph", inevitably takes the form where each connected component is a directed cycle with directed trees branching off of it.

Note that some sort of solution is always possible if ~N~ is even, and always impossible if ~N~ is odd. Therefore, if ~N~ is odd we can immediately output -1. The following explanations deal with the case where ~N~ is even.

Subtask 1

Let ~G~ be the set of all people; let ~S~ be a subset of ~G~ and let ~T = G \setminus S~. In order for ~S~ to be the set of people ♥-shot in any solution, the following conditions must hold:

• If we remove the edges originating from people in ~S~, all connected components in the resulting graph must have at most ~2~ vertices. This is because the final graph can be constructed by only adding edges to this graph, and in the final graph all connected components have ~2~ vertices.
• No person who loves themselves can be in ~T~, because then they will love themselves in the final arrangement, which is not permitted.

If these conditions hold, ~S~ can be used to construct a solution by pairing off the people in connected components of size ~2~ and pairing everyone else off randomly. ~|S|~ arrows will be used. Therefore, a set ~S~ can be the set of people shot if and only if those conditions are met.

To solve the problem, we can iterate over all sets ~S~ and check for this property, then pick the smallest fitting set ~S^*~ and output ~|S^*|~. There are ~2^N~ subsets of ~G~, and checking each set can be done in ~\mathcal O(N)~ time. The complexity is therefore ~\mathcal O(N 2^N)~.

An alternative approach is to use dynamic programming on subsets in ~\mathcal O(N 2^N)~ time.

Subtask 2

In order for everyone to be loved by someone, everyone must be loved by exactly one person. In this subtask, each connected component of the graph takes the form of a cycle. Let's process each component separately, let ~C~ be the number of vertices in the component. It is easy to see that if the component has an even number of vertices, then it is optimal to pair each vertex off with one of its neighbours, using ~\frac C 2~ arrows, unless the component has ~2~ vertices, in which case no arrows are needed. On the other hand, if the component has an odd number of vertices, then it is optimal to pair each vertex but one off with one of its neighbours, pairing the last vertex off with a vertex outside of that component, using ~\lfloor \frac C 2 \rfloor+1~ arrows. The problem can be solved in ~\mathcal O(N)~ time by counting the vertices in each component.

Subtask 3

Since there are no "love polygons", that must mean the cycle in each connected component of the graph consists of one character loving themselves. This means each connected component takes the form of a directed tree with all edges directed towards the root.

We call a set of vertices ~T~ in the forest lucky if and only if:

• For each vertex in ~T~, its parent is not in ~T~;
• For each vertex in ~T~, none of its children are in ~T~;
• For each vertex in ~T~, none of its siblings are in ~T~.

Let ~S^*~ be the set of vertices that are not shot with a love arrow in the optimal solution. Then ~S^*~ is clearly a lucky set: any character in that set will end up in a relationship with the character they initially loved; that is, they will be paired off with their parent in the tree. Let ~v~ be in ~S^*~, then:

• The parent of ~v~ must be shot with an arrow to love ~v~. Therefore the parent of ~v~ is not in ~S^*~.
• All children of ~v~ must be shot with an arrow, otherwise they would end up in a pair with ~v~, but we know ~v~ will be paired off with its parent. Therefore no children of ~v~ are in ~S^*~.
• All siblings of ~v~ must be shot with an arrow, otherwise they would end up in a pair with the parent of ~v~, but we know the parent of ~v~ will be paired off with ~v~. Therefore no siblings of ~v~ are in ~S^*~.

Hence, ~S^*~ is a lucky set. Note that the number of love arrows required is ~N-|S^*|~. Furthermore, given any lucky set ~S~ that doesn't contain roots, we can construct a solution using ~N-|S|~ arrows by pairing the vertices in ~S~ off with their parents and pairing everyone else off randomly. Therefore, if we define ~R~ as the set of lucky sets that don't contain roots, the solution to the problem is:

$$\displaystyle \min_{S \in R} (N-|S|) = N-\max_{S \in R} |S|$$

Our task is therefore to calculate the size of the largest lucky set that doesn't contain any roots. This can be done using dynamic programming.

Let ~L_v~ denote the set of initial lovers (children) of vertex ~v~, excluding vertex ~v~ itself if ~v~ is a root. Define:

• ~mls(v)~ to be the size of the maximum lucky set within the subtree of ~v~ whose member ~v~ itself is not.
• ~\overline{mls}(v)~ to be the size of the maximum lucky set within the subtree of ~v~ whose member ~v~ itself is.

The size of the largest lucky set is then ~\sum mls(r)~ over all roots ~r~. If vertex ~v~ is a leaf, then clearly ~mls(v) = 0~ and ~\overline{mls}(v) = 1~. Let ~v~ be a nonleaf vertex. Then the equation

$$\displaystyle \overline{mls}(v) = 1+\sum_{u \in L_v} mls(u)$$

clearly holds. Lucky sets within the subtree of ~v~ that don't contain the vertex ~v~ can either:

• Not contain any of the children of ~v~. The largest of them has size ~\sum_{u \in L_v} mls(u)~.
• Contain exactly one of the children of ~v~. The largest lucky set containing ~w~, a child of ~v~, has size ~(\sum_{u \in L_v} mls(u))+\overline{mls}(w)-mls(w)~.

All those kinds of lucky sets exist, the largest of them has therefore size:

$$\displaystyle \begin{align*} & \max\left\{\sum_{u \in L_v} mls(u), \max_{w \in L_v} \left(\left(\sum_{u \in L_v} mls(u)\right)+\overline{mls}(w)-mls(w)\right)\right\} \\ &= \max\left\{\sum_{u \in L_v} mls(u), \sum_{u \in L_v} mls(u) + \max_{w \in L_v} \left(\overline{mls}(w)-mls(w)\right)\right\} \\ &= \max\left\{\overline{mls}(v)-1, \overline{mls}(v)-1+\max_{w \in L_v} \left(\overline{mls}(w)-mls(w)\right)\right\} \\ &= \max\left\{0, \max_{w \in L_v} \left(\overline{mls}(w)-mls(w)\right)\right\}+\overline{mls}(v)-1 \end{align*}$$

Therefore,

$$\displaystyle mls(v) = \max\left\{0, \max_{w \in L_v} \left(\overline{mls}(w)-mls(w)\right)\right\}+\overline{mls}(v)-1$$

To sum it up, for any vertex ~v~:

$$\displaystyle mls(v) = \begin{cases} 0 & \text{if }v\text{ is a leaf} \\ \max\left\{0, \max_{w \in L_v} \left(\overline{mls}(w)-mls(w)\right)\right\}+\overline{mls}(v)-1 & \text{otherwise} \end{cases}$$

and

$$\displaystyle \overline{mls}(v) = \begin{cases} 1 & \text{if }v\text{ is a leaf} \\ 1+\sum_{u \in L_v} mls(u) & \text{otherwise} \end{cases}$$

hold. Using those recurrences, we can iterate over all connected components of the graph, do a depth-first search on them and calculate the values of ~\overline{mls}(v)~ and ~mls(v)~ for all vertices ~v~. Finally, we can output ~N-\sum mls(r)~ over all roots ~r~. Each vertex needs to be traversed only once, which gives a runtime of ~\mathcal O(N)~.

Subtask 4

The subtask is solved similarly to subtask 3. We will process each connected component separately. If the cycle of the current component consists of just one character, we will process it the same way as in subtask 3. If the cycle is longer, we pick one arbitrary character. In the optimal solution, that character either is in a relationship with the person they love, or isn't. In both cases, we can eliminate some arcs from the component so that the component becomes a forest of directed trees. Using the solution from subtask 4, we can calculate the number of love arrows needed in both situations and pick the better one. This solves the subtask in ~\mathcal O(N)~. ♥