Maximum Unique Cities

Alice wants to plan a trip through a network of cities connected by bidirectional roads. She wishes to maximize the number of unique cities visited during a single trip. The condition is that the cities must be connected and the road network must contain at least one cycle that allows her to eventually return to an earlier city, thereby visiting all cities.

You are given two integers n and m where n is the number of cities and m is the number of roads. Each road connects two distinct cities. Your task is to determine whether it is possible for Alice to travel through all n cities under the following conditions:

• The graph must be connected (i.e. every city is reachable from any other city).
• The graph must contain at least one cycle (i.e. there exists a path starting and ending at the same city without repeating an edge).

If both conditions are met, output n (representing the maximum unique cities that can be visited). Otherwise, output -1.

Note: The roads are bidirectional.

inputFormat

The first line contains two integers n and m separated by a space, where n represents the number of cities and m represents the number of roads. Each of the following m lines contains two integers u and v, representing a bidirectional road between cities u and v.

Input Format:

n m
u1 v1
u2 v2
...
um vm

outputFormat

Output a single integer: if it is possible for Alice to visit all n cities (i.e. the graph is connected and contains a cycle) then output n; otherwise, output -1.

## sample

4 4
1 2
2 3
3 4
4 1

4