J. Republican
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ buildings in Taco Town, connected by $$$m$$$ roads ($$$2 \leq n \leq 200$$$, $$$n - 1 \leq m \leq 200$$$). The town wants to upgrade some of the roads into highways, but as there are limited resources, constructing a highway requires tearing down an existing (regular) road. For every road, there is a single highway that could be constructed if this road is destroyed. Since highways may require more resources per length than normal roads, the endpoints of the corresponding highway may differ from those of the road. The government of Taco Town wants to maximize the number of highways, but while doing so they must satisfy the following constraints for any pair of buildings $$$a$$$ and $$$b$$$:

  • Buildings $$$a$$$ and $$$b$$$ are reachable via only regular roads (this ensures that citizens do not become too reliant on highways).
  • There is at most one path between buildings $$$a$$$ and $$$b$$$ using only highways (this ensures that citizens do not get too confused when navigating the city).

Please help Taco Town by finding the maximum number of highways that can be constructed with respect to the conditions above!

Input

The first line of input will contain integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 200$$$, $$$n - 1 \leq m \leq 200$$$) — denoting the number of buildings and roads in Taco Town respectively.

The $$$i$$$th of the next $$$m$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, $$$d_i$$$ ($$$1 \leq a_i, b_i, c_i, d_i \leq n$$$, $$$a_i \neq b_i$$$, $$$c_i \neq d_i$$$) — meaning that there is currently a road between buildings $$$a_i$$$ and $$$b_i$$$, and that this road may be replaced with a highway between buildings $$$c_i$$$ and $$$d_i$$$.

Output

Output a single integer, denoting the maximum number of highways that can be constructed with respect to the conditions.

Examples
Input
3 4
1 2 2 3
1 3 1 2
2 3 1 2
3 2 3 2
Output
2
Input
3 3
1 2 2 3
1 3 1 2
2 3 1 2
Output
1