Today there is a party at school. N girls and M boys attend this party. The principal wants to give some presents to the girl and he decides to make the boy do that. Each boy has told the principal the name of the two girls that he wants to give the present to so the principal wants the form teacher to choose some boys to do that. However, he is short in cash now so he wants the number of boys selected is minimum but he also wants all the girls to have at least one present. If you select a boy, then he will give the presents to both of the girls he has chosen.

Input

The first line contains two integers N and M (2 ≤ N ≤ 1000, 1 ≤ M ≤ 1000) which is the number of the girls and boys.

The i-th line of the following M lines contains two integers ai and bi (1 ≤ ai, bi ≤ N) which are the two girls that the i-th boy wants to give present to

Output

One single integer number, which is the minimum boys the form teacher should choose.

Example

Input:
3 3
1 2
2 3
1 3

Output:
2