Longest Scenic Route

You are given an undirected graph representing scenic spots on AoTuo Mountain. There are \(n\) scenic spots and \(m\) trails connecting pairs of spots. Only the spots connected by a trail are considered; isolated spots are not chosen. The visitors do not like to visit any scenic spot more than once, and they can start and end at any spot. Your task is to plan a route (a simple path in the graph) that uses as many trails as possible.

Note: A simple path is one in which no vertex (scenic spot) is visited more than once.

Mathematical formulation:
Given an undirected graph \(G=(V,E)\) with \(|V|=n\) and \(|E|=m\), find the maximum integer \(L\) such that there exists a simple path in \(G\) containing \(L\) edges. In other words, maximize \(L\) where a simple path is a sequence of vertices \(v_1, v_2, \ldots, v_{L+1}\) with \((v_i,v_{i+1})\in E \) for all \(1 \le i \le L\) and all \(v_i\) are distinct.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of scenic spots and trails respectively. The following \(m\) lines each contain two integers \(u\) and \(v\) (1-indexed) indicating there is a trail between spot \(u\) and spot \(v\).

outputFormat

Output a single integer which is the maximum number of trails in any simple path.

sample

3 2
1 2
2 3

2