Consider the directed graph \(G\) with \((N\times W)\) vertices such that:

• The vertices is represented by integer pairs \((x,w) \ (1\leq x\leq N,1\leq w\leq W)\), and
• For any \(1\leq x,y\leq N\) and \(1\leq w\leq W\), there is a directed edge \((x,w)\to(y,w\bmod W+1)\) if they satisfy the following conditions:
  • \(x=y\), or cities \(x\) and \(y\) are directly connected by a road
  • \(S_{x,w}\) and \(S_{y,w\bmod W+1}\) are both o.

If we associate vertex \((x,w)\) with Takahashi staying at city \(x\) on day \(w\), he can keep moving if and only if \(G\) has a cycle.

One can detect a cycle in a directed graph using DFS (Depth-First Search) or in the manner of topological sort, in \(O((N+M)W)\) time.

Sample code (C++) Sample code (PyPy)