Solved!
Difficulty: D2C

Pretty basic exercise problem from FLA

This is an easy version of Ep. 68.
If you prefer harder problems, please visit here.

Meeting Point

Given a directed graph G of n vertices and m edges. A single vertex S is called the starting point and a single vertex T is called the finish point. A vertex u is called midpoint if there exists a walk Sv_1v_2v_3...v_{2n+1}T where v_{n+1}=u.

Find all midpoints.

Recall that a walk is a node sequence where for all 1\leq i<n we have v_iv_{i+1}\in E. Duplicate vertices are allowed in a walk.

Constraints

n,m\leq 1000

Hint

Run BFS on a product graph with n\times n vertices. Your starting point is (S,T). Two vertices (u,v),(x,y) has an edge iff ux\in E\wedge yv\in E