#include using namespace std; struct Edge { typedef int CostType; const static int cost = 1; int from, to; Edge(int from, int to) : from(from), to(to) {}; }; template struct WeightedEdge : public Edge { typedef Cost CostType; Cost cost; WeightedEdge(int from, int to, Cost cost = 0) : Edge(from, to), cost(cost) {} }; template struct ResidualEdge : public Edge { typedef Capacity CapacityType; Capacity cap; int rev; ResidualEdge(int from, int to, Capacity cap) : Edge(from, to), cap(cap) {} ResidualEdge reverse() const {return ResidualEdge(to, from, 0);} }; template struct WeightedResidualEdge : public ResidualEdge { Cost cost; WeightedResidualEdge(int from, int to, Capacity cap, Cost cost) : ResidualEdge(from, to, cap), cost(cost) {} WeightedResidualEdge reverse() const {return WeightedResidualEdge(this->to, this->from, 0, -cost);} }; template class Graph { public: typedef Edge EdgeType; virtual int size() const = 0; template void addEdge(Args...) {} template void addUndirectedEdge(Args...) {} virtual vector getEdges() const = 0; virtual vector getEdges(int from) const = 0; virtual vector getEdges(int from, int to) const = 0; virtual int getDegree(int v) const = 0; }; template class AdjacencyList : public Graph { protected: vector> graph; public: AdjacencyList(int n) : graph(n) {} int size() const { return graph.size(); } template void addEdge(Args... args) { Edge edge(args...); graph[edge.from].emplace_back(edge); } template void addUndirectedEdge(Args... args) { Edge edge(args...); addEdge(edge); swap(edge.from, edge.to); addEdge(edge); } vector getEdges() const { vector res; for (const auto& edges : graph) { res.insert(res.end(), edges.begin(), edges.end()); } return res; } vector getEdges(int from) const { return graph[from]; } vector getEdges(int from, int to) const { vector res; for (const auto& edge : graph[from]) { if (edge.to == to) res.emplace_back(edge); } return res; } int getDegree(int v) const { return graph[v].size(); } vector& operator[](int v) { return graph[v]; } }; template class Search { protected: typedef typename Graph::EdgeType Edge; const Graph graph; vector visited; virtual void push(const State&) = 0; virtual State next() = 0; virtual bool isRunning() = 0; virtual void visit(const State&) {} virtual bool canPruning(const State&) {return false;} public: Search(const Graph& graph) : graph(graph), visited(graph.size(), false) {} void solve(int from) { push(State(from)); while (isRunning()) { State now = next(); int pos = now.getPos(); if (visited[pos]) continue; visited[pos] = true; visit(now); for (const Edge& edge : graph.getEdges(pos)) { State nextState = now.next(edge); if (visited[nextState.getPos()]) continue; if (canPruning(nextState)) continue; push(nextState); } } } bool isReachable(int v) { return visited[v]; } }; template struct WeightedBFSState { typedef typename Edge::CostType Cost; Edge edge; Cost cost; WeightedBFSState(int pos, int prv = -1) : edge(prv, pos), cost(0) {} WeightedBFSState(const Edge& edge, Cost cost) : edge(edge), cost(cost) {} WeightedBFSState next(const Edge& edge) const { return WeightedBFSState(edge, cost + edge.cost); } int getPos() { return edge.to; } }; template> class WeightedBFS : public Search { protected: typedef typename Graph::EdgeType Edge; typedef typename Edge::CostType Cost; private: Cost now; deque> que; void push(const State& state) { if (state.cost - now >= que.size()) que.resize(state.cost - now + 1); que[state.cost - now].push(state); } State next() { State now = que[0].front(); que[0].pop(); return now; } bool isRunning() { while (!que.empty() && que[0].empty()) { que.pop_front(); ++now; } return !que.empty(); } public: WeightedBFS(const Graph& graph) : Search(graph), now(0) {} }; namespace weighted_bfs_distance { template class WeightedBFSDistance : public WeightedBFS { private: typedef WeightedBFSState State; void visit(const State& state) { if (state.edge.from != -1) dis[state.edge.to] = dis[state.edge.from] + state.edge.cost; } public: vector dis; WeightedBFSDistance(const Graph& graph) : WeightedBFS(graph), dis(graph.size(), 0) {} }; } template inline weighted_bfs_distance::WeightedBFSDistance weightedBFSDistance(const Graph& graph, int from) { weighted_bfs_distance::WeightedBFSDistance bfs(graph); bfs.solve(from); return bfs; } int main() { int w, h; cin >> w >> h; vector c(h); for (auto& i : c) cin >> i; AdjacencyList> graph(w * h); for (int i = 0; i < h; ++i) { for (int j = 0; j < w - 1; ++j) { graph.addEdge(i * w + j, i * w + j + 1, c[i][j + 1] == '.' ? 0 : 1); } for (int j = 0; j < w - 1; ++j) { graph.addEdge(i * w + j + 1, i * w + j, c[i][j] == '.' ? 0 : 1); } } for (int i = 0; i < h - 1; ++i) { for (int j = 0; j < w; ++j) { graph.addEdge(i * w + j, i * w + j + w, c[i + 1][j] == '.' ? 0 : 1); } for (int j = 0; j < w; ++j) { graph.addEdge(i * w + j + w, i * w + j, c[i][j] == '.' ? 0 : 1); } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (c[i][j] == '.') { auto dis = weightedBFSDistance(graph, i * w + j).dis; int res = 0; for (int a = 0; a < h; ++a) { for (int b = 0; b < w; ++b) { if (c[a][b] == '.') res = max(res, dis[a * w + b]); } } cout << res << endl; return 0; } } } }