게임 지도

ICPC-World는 세계 정복을 목표로 하는 롤플레잉 게임이다. 게임 지도는 여러 도시로 이루어진다. 두 도시 사이에는 도로가 많아야 하나 있고, 모든 도로는 양방향이다. 도로로 이어진 두 도시는 서로 이웃이라고 부른다. 각 도시에는 이웃이 하나 이상 있고, 모든 도시는 도로를 따라 서로 오갈 수 있다. 플레이어는 아무 도시에서나 시작할 수 있다. 지금 머무는 도시를 정복한 다음에는 그 도시의 이웃 중 하나로 옮겨 가서 다음 차례에 그 도시를 정복한다.

찬수는 게임을 시작하기 전에 정복할 도시 목록을 미리 정한다. 이번에는 다음 조건을 지키면서 도시를 최대한 많이 고르려고 한다. 정복할 순서대로 적은 목록을 $(c_0, c_1, \ldots, c_{k-1})$이라고 하자.

• 목록에 있는 도시는 모두 다르다. 즉 $i \neq j$이면 $c_i \neq c_j$이다.
• $c_i$와 $c_{i+1}$은 서로 이웃이다.
• $c_{i+1}$의 이웃 수는 $c_i$의 이웃 수보다 많다.

마지막 두 조건은 $i = 0, 1, \ldots, k-2$에 대해 모두 성립해야 한다.

예를 들어 아래 그림의 지도를 보자. 도시는 여섯 개이고 도로는 0-1, 0-4, 1-2, 1-3, 1-4, 1-5, 2-5, 3-4, 4-5로 아홉 개다. 도시 0의 이웃은 둘이고 도시 1의 이웃은 다섯이다. 조건을 만족하는 가장 긴 목록은 $(2, 5, 4, 1)$이고, 도시 네 개를 정복한다.

도시가 $n$개인 지도가 주어질 때, 찬수가 정복할 수 있는 도시의 최대 개수, 즉 조건을 만족하는 가장 긴 목록의 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 주어진다 ($1 \le n \le 100{,}000$, $n-1 \le m \le 300{,}000$). 도시에는 $0$부터 $n-1$까지 번호가 붙어 있다. 다음 $m$개 줄에는 도로가 잇는 두 도시의 번호 $i$와 $j$가 주어진다 ($0 \le i \neq j \le n-1$).

찬수가 정복할 수 있는 도시의 최대 개수를 한 줄에 출력한다. 도시 하나만 담은 목록도 조건을 만족하므로 답은 항상 $1$ 이상이다.