\problemname{On Average They're Purple}

\ifdefined\pacnw
\illustration{0.3}{coloringgraphedgesgame2.png}{}
\else
\illustration{0.3}{coloringgraphedgesgame/problem_statement/coloringgraphedgesgame.png}{}
\fi

\noindent
Alice and Bob are playing a game on a simple connected graph with $N$
nodes and $M$ edges.

Alice colors each edge in the graph red or blue.

A path is a sequence of edges where each pair of consecutive edges have a
node in common.
If the first edge in the pair is of a different color than the second
edge, then that is a ``color change.''

After Alice colors the graph,
Bob chooses a path that begins at node $1$ and ends at node $N$. He can
choose any path on the graph, but he wants to minimize
the number of color changes in the path. Alice wants to choose an edge coloring
to maximize the number of color changes Bob must make.
What is the maximum number of color
changes she can force Bob to make, regardless of which path he chooses?

\section*{Input}

The first line contains two integer values $N$ and $M$ with $2 \le N \le
100\,000$ and $1 \le M \le 100\,000$. The next $M$ lines contain two integers
$a_i$ and $b_i$ indicating an undirected edge between nodes $a_i$ and $b_i$ ($1
\le a_i, b_i \le N$, $a_i \not= b_i$).

All edges in the graph are unique.

\section*{Output}

Output the maximum number of color changes Alice can force Bob to make on his
route from node $1$ to node $N$.
