889. Maximum Graph Power

0

Medium

The maximum power of a graph is determined by the highest power among all pairs of distinct vertices.

The power of two different vertices is defined as the total number of directly connected edges to either vertex. If an edge is directly connected to both vertices, it is only counted once.

A graph with n vertices and a certain number of edges connecting them is given. Each edge[i] = [ai, bi] indicates a bidirectional edge between vertices ai and bi.

Given the integer n and the array edges, find and return the maximum power of the graph.

The power of two different vertices is defined as the total number of directly connected edges to either vertex. If an edge is directly connected to both vertices, it is only counted once.

A graph with n vertices and a certain number of edges connecting them is given. Each edge[i] = [ai, bi] indicates a bidirectional edge between vertices ai and bi.

Given the integer n and the array edges, find and return the maximum power of the graph.

Input Format

The first line of the input contains two integers n and m, representing the number of vertices and edges respectively.
The following m lines contain two integers ai and bi, indicating a bidirectional edge between vertices ai and bi.

Output Format

Return an integer representing the maximum power of the graph.

Example

Input

4 4
0 1
0 3
1 2
1 3

Output

4

Constraints

Loading...

View Submissions

Console