Minimum Specific Intersections

You are given an undirected graph representing intersections and roads. The graph has n intersections and m roads. Each road connects two distinct intersections.

An intersection is considered specific if its degree (number of connected roads) is exactly 3.

Your task is to perform a bipartite partition (i.e. assign one of two colors to each intersection so that every road connects intersections of different colors) and then count the number of specific intersections in each partition. The answer is the minimum of these two counts, mathematically represented as:

\(\min(C_0, C_1)\)

where \(C_0\) and \(C_1\) are the counts of intersections with exactly 3 roads in the two partitions respectively.

You can assume that the graph is connected.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two space-separated integers n and m, representing the number of intersections and roads respectively.
2. Each of the next m lines contains two space-separated integers u and v, indicating that there is a road connecting intersections u and v.

outputFormat

Output a single integer to standard output (stdout): the minimum number of specific (degree exactly 3) intersections in either partition after a valid bipartite coloring of the graph.

## sample

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

0