프로그램 명: coci_staza
제한시간: 1 초
[문제요약] 가징 긴 패스를 찾는 것이 문제이다. 어떤 노드에서 시작해도 되나 끝은 1 로 끝나야 하고
패스 상의 정점은 중복이 가능하나 패스는 중복되어서는 안된다.
A bicycle race is being organized in a country. The transport network of the country consists of N cities
numbered 1 through N, with M bidirectional roads connecting them.
We will use the following terms:
- A path is a sequence of roads in which each road starts in the city the preceding road ended in.
- A simple path is a path which never visits a city more than once.
- A ring is a simple path ending in the same city it started in.
The network is such that there is at least one path between every pair of cities. Additionally, every
road in the network is part of at most one ring.
Your task is to find the longest path for the race satisfying two constraints:
- The path may begin in any city, but must end in city 1.
- The path may visit a city more than once, but it must not contain any road more than once.
입력
The first line of input contains two integers N and M (2 ≤ N ≤ 10 000, 1 ≤ M ≤ 2N-2) - the numbers
of cities and roads in the network.
Each of the following M lines contains two different integers A and B (1 ≤ A, B ≤ N). These numbers
indicate that there is a bidirectional road between cities A and B. No two cities will be directly
connected by more than one road.
출력
Output the length of the longest race path on a single line.
입출력 예
input
4 3
1 2
1 3
2 4
output
2
input
6 6
1 2
1 3
2 4
3 4
3 5
5 6
output
5
input
5 6
1 2
2 3
3 4
4 5
5 3
3 1
output
6
출처:coci 2007-2008 contest1
[질/답]
[제출 현황]
[푼 후(0)]