Strange matter is a mysterious and exotic substance that scientists believe to be more stable than ordinary matter. This gives it a terrifying property: anything it touches is transformed into strange matter too.

While your team are distracted with the stars, your ship brushes against a pocket of strange matter. It's breached room ~1~ of your ship, and it's spreading fast. If it reaches your team in room ~n~, all hope is lost.

Your ship consists of ~n~ rooms, labeled from ~1~ to ~n~, connected by ~m~ bidirectional passages. The strange matter spreads through these passages. Fortunately, you can destroy exactly one passage, permanently severing that connection.

You want to destroy a single passage so there is no longer any path from room ~1~ to room ~n~, cutting off the strange matter and saving your team. How many different ways can you achieve this?

Input

The first line consists of two integers ~n~ ~(1 \leq n \leq 10^5)~ and ~m~ ~(n-1 \leq m \leq 10^5)~, the number of rooms in the ship and the number of passages, respectively.

The next ~m~ lines contain ~a~ and ~b~ ~(1 \leq a, b \leq n)~, indicating that rooms ~a~ and ~b~ are connected by a passage.

Output

Output the number of ways to destroy exactly one passage, so that rooms ~1~ and ~n~ are no longer connected.

Clarifications

• Your ship is completely connected, no room begins isolated from any other.
• You must destroy a passage.
• This problem only differs from Strange Matter I in the constraints.

Example

Input 1

5 5
1 2
1 3
2 3
3 4
4 5

Output 1

2

You can either destroy the passage from room ~3 \to 4~, or room ~4 \to 5~, to save the team.

Input 2

4 6
1 2
1 3
1 4
2 2
2 3
3 4

Output 2

0

There will always be a path from room ~1~ to room ~4~, regardless of which passage you destroy.