### 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

## Input4 3 1 2 1 3 2 4 ## Output2 |
## Input6 6 1 2 1 3 2 4 3 4 3 5 5 6 ## Output5 |
## Input5 6 1 2 2 3 3 4 4 5 5 3 3 1 ## Output6 |

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)

It's quiet in here...