Game Map

ICPC-World is a role playing game whose goal is to conquer the world. A game map consists of several cities. Between any two cities there is at most one road, and every road is bidirectional. Two cities joined by a road are called neighbors. Every city has one or more neighbors, and all cities are reachable from each other along the roads. A player may start at any city. After conquering the city where the player stands, the player moves to one of its neighbors and conquers that city at the next stage.

Chansu fixes the list of cities he will conquer before he starts the game. This time he wants to choose as many cities as possible while keeping the conditions below. Let $(c_0, c_1, \ldots, c_{k-1})$ be the list in conquest order.

• All cities in the list are distinct, that is, $c_i \neq c_j$ whenever $i \neq j$.
• $c_i$ and $c_{i+1}$ are neighbors.
• The number of neighbors of $c_{i+1}$ is greater than the number of neighbors of $c_i$.

The last two conditions must hold for every $i = 0, 1, \ldots, k-2$.

For example, look at the map in the figure below. It has six cities and nine roads: 0-1, 0-4, 1-2, 1-3, 1-4, 1-5, 2-5, 3-4, 4-5. City 0 has two neighbors and city 1 has five neighbors. The longest list that satisfies the conditions is $(2, 5, 4, 1)$, which conquers four cities.

Given a game map with $n$ cities, write a program that finds the maximum number of cities Chansu can conquer, that is, the length of the longest list satisfying the conditions.

The first line contains the number of cities $n$ and the number of roads $m$ ($1 \le n \le 100{,}000$, $n-1 \le m \le 300{,}000$). The cities are numbered from $0$ to $n-1$. Each of the next $m$ lines contains two integers $i$ and $j$, the cities joined by one road ($0 \le i \neq j \le n-1$).

Print the maximum number of cities Chansu can conquer on one line. A list holding a single city already satisfies the conditions, so the answer is always at least $1$.