Let's call a line valid if it is parallel with ~x~ or ~y~-axis and there is a point located on it.

The lines and points can be represented by a bipartite graph. The nodes on the left side of the graph represent valid lines parallel with ~x~-axis, and the nodes on the right side represent valid lines parallel with ~y~-axis. For each input point ~(x, y)~ we can set an edge between the line ~x~ from the left side and the line ~y~ from the right side.

Now the game can be presented like this:

• in the first move Mirko chooses a node and removes it from the graph
• after that, Slavko removes any node not removed so far connected to the previously removed node
• next, Mirko does the same and they repeat this alternately
• the loser is the one who cannot remove anything more

Since this is related to bipartite graphs, it is expected that the solution will be connected with maximum matchings.

Exactly! If there is a perfect matching (where each node from the graph is paired with exactly one other node with which it shares an edge), Slavko will win. Otherwise, Mirko wins.

Why? Let us presume that there is a perfect matching in our graph. It doesn't matter which node Mirko chooses – it will always have an existing match on the other side of the graph, making Slavko's next move possible. Therefore, whatever Mirko chooses, Slavko can fight back. This makes Mirko the designated loser.

In case there isn't a perfect matching, we can analyse the maximum one. Mirko can in the beginning choose whichever nonmatched node. Now the node Slavko chooses will surely have a pair (if it doesn't have a pair, we could improve the maximum matching by connecting Mirko's and Slavko's played out nodes – contradiction), so Mirko can use the same tactics as Slavko in the previous paragraph.