Practice Depth first search and Ascii art with the exercise "Longest Road"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

Determine which player in a rectangular "Settlers of Catan" themed game board has the longest road.

Given an ascii game board:

aa##b
#A##B
#aa#b
##a##

The lower case letters "a" denote a road belonging to player A.
Uppercase letters denote a settlement.

If a player has at least 5 consecutive (non-repeating) roads then they can be awarded the "longest road" victory points.
Roads connected diagonally are not considered consecutive. Roads can be linked together by settlements, but the settlements do not count towards the total length of the player's roads. In the above example player A would have the longest road with a length of 5.

The input will never include the case where multiple players are tied for longest road.

Loops and branches
A road may form a loop or branch out in multiple directions. In all cases the longest possible consecutive link of roads is used to determine the players' longest roads.

Inspired by the board game "Settlers of Catan" by Klaus Teuber.
Image by dograapps from Pixabay.

Input

Line 1: Integer n the length of the square board.
Next n lines: String of characters representing the game board. # represents an open space. Lowercase letters represent roads, and uppercase letters represent settlements.

Output

Output the capital letter of the player with the longest road, and the length of the road, e.g. A 6.
If no player has the longest road then output the number 0.

Constraints

5 ≤ n ≤ 10

Example

Input

5
#a###
#a###
#a###
#aa##
##a##

Output

A 6

Solve it

A higher resolution is required to access the IDE