Passable Paths (hard version)

CodeForces - 1702G2