Problem 882 · Hard
Dijkstra over original nodes, then count how many subdivision nodes each edge lends from both ends.
Open the interactive visualisation