Editorial for Mock CCC '18 Contest 1 S4 - A Graph Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
The most straightforward solution is to construct each graph and then do a BFS from ~S~ to ~T~. This runs in ~\mathcal O(K(N+M))~ time.
We can reduce this to ~\mathcal O(M^2)~ time by noticing that there are only ~\mathcal O(M)~ relevant graphs to construct - namely when an edge becomes eligible or when an edge becomes unavailable.