For any line ~A~-~B~ we deduce: each Krump's selection of city ~A~ or city ~B~ changes its existence, so its final existence depends only on the parity of the number of selections of cities ~A~ and ~B~. Given this fact, it is sufficient to assume that Krump selects each city zero or one time (selection or non-selection), which greatly simplifies the task.

We investigate two options: Krump either selects city ~1~, or he doesn't. For each of the possibilities, we will check whether they can lead to a complete graph. If we've fixed the selection (or non-selection) of city ~1~, for each other city ~K~ we can easily determine if it needs to be selected, considering the parity that must enable the existence of flight route ~1~-~K~. This way, we determine the selections or non-selections of all cities from ~2~ to ~N~. Since we've only ensured the existence of flight routes ~1~-~K~, we will check the existence of all other lines, and if all of them exist, the answer is DA (Croatian for "yes").

An alternative solution is the following: the answer is DA (Croatian for "yes") if and only if the initial graph consists of exactly two components, each of them being a complete graph (clique). The proof is left as an exercise for the reader.