You recently started to go running in your free time. You got the shoes, you got the tracking app, and you even picked up your first injury a couple of days ago. Overall, you are really starting to like this new hobby of yours.

So far, your training routine was to run from your office to your home along the streets of your town. The town consists of $$$n$$$ intersections, numbered from $$$1$$$ to $$$n$$$, which are connected by $$$m$$$ bidirectional streets of equal length. Your office is located at intersection $$$1$$$, and your home is at intersection $$$n$$$.

As the computer scientist you are, you were of course following a shortest path. However, studies indicate that you should not just train to complete the same route in a faster time, but also to complete longer routes. Given that the last time you experimented with new training methods did not go so well, you want to take this new approach slowly. Therefore, you are looking for a route from your office to your home that is exactly one street longer than your current route. To keep the run interesting, you also want to avoid visiting any intersection more than once. Determine whether such a new training route exists.

Visualization of a possible new training route in the first sample.