COCI 2007/2008, Contest #1

Task STAZA

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.

Input

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

Output the length of the longest race path on a single line.

Examples

4 3
1 2
1 3
2 4

2

6 6
1 2
1 3
2 4
3 4
3 5
5 6

5

5 6
1 2
2 3
3 4
4 5
5 3
3 1

6

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)