We will call Bornholm and Gotland ~A~ and ~B~ respectively. The first step of our algorithm is setting all the teleports on ~A~ in receiving mode, and all teleports on ~B~ in sending mode.

Why is this solution not good? The only thing that is wrong is that some receiving teleports on ~A~ are useless — there are no teleports sending to them. We will maintain this invariant — after each step the solution will be OK except that some receiving teleports on ~A~ will be useless.

In each step we choose a receiving teleport on ~A~ with no teleports sending to it. If there are no such teleports, we are finished. Let's call the teleport we have chosen ~x~. We switch the teleport ~x~ to sending mode. Let ~y~ be the destination of ~x~ — ~y~ is a teleport on ~B~. If ~y~ is in receiving mode, all is fine — the invariant is true. Otherwise we just switch ~y~ to receiving mode. We can make another receiving teleport on ~A~ useless this way, but the invariant is still true.

At the end there are no useless teleports left, so we have a correct solution.

At each step the number of receiving teleports on ~A~ decreases by ~1~, so we will make at most ~m~ steps.

To be able to make each step in ~\mathcal O(1)~ time, we introduce an array ~inDegree~, in which we store for each teleport on ~A~ the number of teleports sending to it. We also keep track of all useless receiving teleports on ~A~ — in the sample solution they are kept on a stack. In each step we just take a teleport from the stack, switch it to sending mode, possibly change the mode of its destination teleport and update one entry in the array ~inDegree~.

Reading the input and the initial step take ~\mathcal O(m+n)~ time, therefore time complexity of the whole algorithm is ~\mathcal O(m+n)~.