AtCoder Beginner Contest 151 Problem D

Problem Statement : Problem Link

Solution : Run BFS for every free path, you get AC (constraints are very small) MySolution

The Actual Question : What is the solution of this problem when the constraints are large ? because this multiple-BFS-approach will cause TLE. Is the solution even possible if constraints are large ? Please help.

I was thinking about using double-BFS (The first BFS gives me the coordinates of the free block farthest away from the start coordinates. The second BFS takes those coordinates and calculates the max distance.) to calculate longest path but that method gives solution for a tree not a graph. It will fail for test cases like : -
3 3


More info. about this double-BFS method : Longest path in an undirected tree