URI Online Judge | 3169

Hitting Retreat

By Aléxis Toigo, URI BR Brazil

Timelimit: 2

Evergreen who is one of Noel's elves, and who is known for playing tricks on him (See problem 2722) as one of his hobbies. But this year, due to the pandemic, he cannot execute his pranks, as Noel belongs to the group at risk, and an end to also fulfill social isolation in the North Pole.
As he was bored and with nothing to do, he decided that he would start playing an MMORPG with his other elf friends.
To make it easier for the elves to join the game and for everyone to play together and help each other in the progress of the game, Evergreen decided to create a guild in the game, he brought together all the P-1 elves players who are also new to the game and decided to go and defeat a very strong Monster, but as the P-1 members and Evergreen are still at low level, seeing that they could not defeat the Monster, they had to retreat to avoid dying and losing XP and their items that took so long to get ( in this game the death penalty is the loss of XP and items). A Monster area consists of a grid of NxN cells. Evergreen and his fellow elves can only walk in the origins of the North, South, East and West. There are also P portals, one for each guild member. However, each portal can only be used once, that is, when a player enters it, it disappears, a player can go through the cell where there is a portal and decide not to enter it. In addition, due to the great battle, the Monster also ended up destroying cells, making them inaccessible. Since all players are low on health and have a collection of healing potions, you must calculate how many moves the most distant player will go through if the main portals are chosen optimally. If any player is unable to access your portal you must print -1.

Grid legend:
    . -Empty cell;
    # -Destroyed cell;
    G - Member of the Guild or Evergreen
    X -Portal

All positions of G and X are guaranteed to be in different classifications.

In this example we have N = 4 and P = 2, where the best way is for the player of position [3, 4] to go to the portal of position [1, 1] with the cost of 5 moves, and the player of position [4 , 4] go to the portal [3, 2] generating a cost of 3 movements. The answer for this case is then 5, which is the longest distance a player will have to travel. Because if the player in position [3, 4] decides to go to the portal [3, 2] with the cost of 2 moves, the player in position [4, 4] will have to go to the portal in position [1, 1] generating a cost of 6 movements which is not the optimal solution, because the player with the highest cost is 6, being higher than if the portals chosen as mentioned above the answer is then 5.


The input consists of T test cases, in the second row two values N and P, where (4 <= N <= 100), which is the dimensions of the grid, and (2 <= P <= 10) the number of members of the guild including Evergreen. Each of the next N lines contains N characters each that will fill the grid.


For each case, print the greatest distance of movements if the players choose the portals in the best possible way, if it is not possible to print -1.

Input Sample Output Sample

4 2
5 5