Statement

You may recall that Edoardo, who has recently been hired by the Municipality of Milan as an Air Traffic Control Operator, is working on the paper-plane project. He has already built T control towers and shot down every obstacle to ease the flight of the planes. However, the project is still not going well: there are too many other things in the air at the same time as the paper planes! Edoardo has been working closely with the authorities in order to work out a solution, and the only option available is to pay for reserving some air corridors for the sole use of this project. Milan can be represented by a square grid of size N × N, where each cell can be either: (1) an empty space, represented with a "." in input; (2) a control tower, represented with a "T" in input. The control tower placed on cell (i_1, j_1) can throw a paper plane towards any other control tower placed on cell (i_2, j_2), using a dedicated air corridor...