## Problem H. Hype spreading ≡

• problems
 Author: A. Klenin Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

One famous car race takes place on a stadium with a racetrack. Spectators watching the race sit on a stand consisting of H rows with W seats each. During the race, some seats are occupied by spectators, and others are empty.

Marketing research demonstrated that if one spectator will loudly shout out a nicely rhymed slogan, spectators on seats located immediately to the left, right, above and below him will repeat it. Their neighbors, in turn, will catch up, and the slogan will spread throughout the stand.

An advertisement company invented a new slogan and wants it to spread among as many spectators as possible. To simulate "spontaneous" appearance of the slogan the company hired an agent who will move to one of the unoccupied seats and shout the slogan from there.

You program must determine the position of the agent which will result in maximum slogan penetration.

### Input file format

Input file contains integers W H in the first line, followed by H lines of W characters each.

Each character is either a '.' (ASCII 46) or '#' (ASCII 35), denoting free and occupied seat correspondingly.

There is at least one free seat.

### Output file format

Output file must contain two integers — x y, denoting seat number and row number for the agent to take. Rows are numbered starting from 1, top to bottom. Seats are numbered starting from 1, left to right. If there are several optimal solutions, output any of them.

2 ≤ W, H ≤ 2000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2
#.
.#
2 1
2
5 5
..#.#
..###
#..##
#.##.
#....
2 4
3
6 4
######
.....#
..##.#
...#.#


3 2

### Explanation

Построим граф, вершинами которого будут занятые места, а ребро между ними будем проводить в случае, если у двух мест имеется общая сторона. Выделим компоненты связности полученного графа (например, с помощью поиска в глубину) и для каждой компоненты связности определим её мощность. Процесс распространения слогана, как следует из условия задачи, таков, что если его подхватывает один из зрителей, он распространяется по всей компоненте связности, соответствующей этому зрителю.

Переберём все свободные клетки. Для каждой свободной клетки рассмотрим соседние с ней вершины графа и их компоненты связности. Количество зрителей, которые подхватят слоган, будет равно суммарной мощности рассмотренных компонент связности.

При реализации следует аккуратно исключить многократный учёт одной и той же компоненты связности, в случае если для заданной клетки эта компонента имеет более одного соседа.

0.099s 0.012s 13