VPARTY - Party At School

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

Added by:Phenomenal
Date:2009-02-16
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IOICAMP

hide comments
2014-06-10 22:54:02 Deepak
my solution fails on 10th judge. Can @phenomenal please hint me what am I missing..??
2013-06-25 13:47:57 kunal keshwani
@admin i want to know any test case in which my code is giving wrong ans..
2013-06-17 16:26:53 Arpit Temani
more test cases plz
2011-01-21 02:20:57 Omar Castaneda Infante
If kids are not enough to give all the girls
2010-04-07 02:34:25 Lewin Gan
you can't assume that, but you can just swap them if you really feel like you need to
2009-12-19 16:30:23 Seshadri R
Can it be assumed that ai < bi?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.