Trasa

시간 제한1초메모리 제한1024 MB

요약

무방향 그래프에서 내부 정점이 경로 밖의 간선을 갖지 않는 가장 긴 단순 경로 또는 단순 사이클의 길이를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 동적 계획법, 트리
정답자: 아직 제출이 없습니다

문제

Dviratininkų draugija paprašė Vytauto padėti sukonstruoti dviračių plento varžyboms skirtą trasą, kuri būtų kaip įmanoma ilgesnė. Vytautas gavo žemėlapį, kuriame pažymėta N miestų ir M juos jungiančių kelių.

Trasa yra miestų seka a1, a2, . . . , ak, tenkinanti tokias sąlygas:

visos gretimų miestų poros (a1 ir a2, a2 ir a3, ..., ak−1 ir ak) yra sujungtos keliu; trasa eina šiais keliais;
trasoje nėra pasikartojančių miestų (vienintelė leidžiama išimtis – žiedinė trasa, kuomet pradinis ir galinis trasos miestas sutampa, t.y. a1 = ak);
trasa negali eiti tuo pačiu keliu du kartus;
trasos vidiniai miestai (t.y. a2, a3, ..., ak−2, ak−1) neturi kitų žemėlapyje pažymėtų kelių, išskyrus tuos, per kuriuos eina trasa.

Parašykite programą, padėsiančią Vytautui rasti ilgiausią leistiną trasą. Trasos ilgis lygus ją sudarančių kelių skaičiui.

입력

Pirmojoje eilutėje pateikiami du sveikieji skaičiai – miestų skaičius N ir miestus jungiančių kelių skaičius M.

Tolesnėse M eilučių pateikiama po du sveikuosius skaičius, kurie nurodo miestų, tarp kurių yra tiesioginis kelias, numerius. Miestai numeruojami nuo 1 iki N. Visi keliai – abipusiai. Tarp bet kurios miestų poros bus daugiausiai vienas kelias.

출력

Išveskite vienintelį sveikąjį skaičių – ilgiausios leistinos trasos ilgį.

제한

2 ≤ N ≤ 1000
1 ≤ M ≤ N(N − 1)/2

예제2

예제 1
입력
```
6 7
1 2
2 3
3 4
3 5
5 4
4 6
5 6
```
예상 출력
```
2
```
예제 2
입력
```
9 6
1 2
3 1
2 4
4 3
4 5
6 7
```
예상 출력
```
4
```