Vì Marisa và Reimu phải di chuyển liên tục nên khoảng cách cả 2 di chuyển phải là số chẵn.

Từ ý trên, ta có thể biến đổi bài toán thành tìm đường đi ngắn nhất từ đỉnh $a$ tới đỉnh $b$ và khoảng cách phải là số chẵn.

Ta gọi $d[u][parity]$ là khoảng cách ngắn nhất từ $a$ đến $u$ và khoảng cách này có tính chẵn lẻ là `parity`.
Ta chuyển trạng thái từ $[u][parity]$ -> $[v][(parity + 1) \bmod 2 ]$
Vì 1 lần Marisa và Reimu di chuyển liên tục nên đáp án sẽ phải chia $2$.