Let's build a graph, where vertices are cities, and edges are railways. Note that the answer is always $$$0$$$ or $$$1$$$, since we can build a simple path from $$$1$$$ to $$$n$$$, where each odd edge has the sign "+", and each even edge has the sign "-".

After that, the graph can be one of two types:

1. The graph does not contain cycles of odd length. Then the graph is bipartite. Let vertex $$$1$$$ be in the first part (if not, then we relabel parts). Note that, because of this, the current time is always even in the first part and odd in the second one. Then the solution above will work here, since the parity of the path's edges is equal to the parity of an answer.
2. The graph contains a cycle of odd length. Suppose we calculated a simple path with an answer of $$$1$$$. Then we can improve the answer by going to the odd cycle, going through it with total time $$$-1$$$, and getting back to the simple path. As a result, the time decreases to $$$0$$$, which is optimal.

In the end, we need to determine whether the graph contains a cycle of odd length or not, and process specific graph type, which takes $$$O(n + m)$$$ time.