Giải bài trực tuyến

Sau kì thi Marathon, thầy My đã quyết định tổ chức một buổi dạ hội nho nhỏ cho các thí sinh. Trong buổi dạ hội này sẽ có N bạn nữ và M bạn nam. Để không khí thêm phần vui vẻ thì thầy My đã nghĩ ra tiết mục các bạn nam tặng hoa cho các bạn nữ. Mỗi bạn nam sẽ đưa cho ban tổ chức danh sách 2 bạn nữ mà bạn đó muốn tặng hoa nhất. Tuy nhiên tiền tài trợ cho buổi dạ hội không còn nhiều (vì đã phải dành hầu hết để trao giải thưởng). Nhưng ban tổ chức cũng không muốn bạn nữ nào không được nhận hoa. Thầy My đã giao việc này cho Mr.Hải Minh, và anh ta đang rất bối rối vì không biết làm thế nào.

Bạn hãy giúp Mr. Hải Minh chọn ra ít bạn nam nhất đứng ra đại diện cho các bạn nam để tặng hoa các bạn nữ sao cho bạn nữ nào cũng được tặng hoa. Biết rằng mỗi bạn nam được chọn sẽ tặng hoa cho cả hai bạn nữ trong danh sách của bạn đó.

Input

Dòng đầu ghi hai số N và M. (2 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)

Dòng thứ i trong M dòng tiếp theo ghi hai số ai và bi là hai bạn nữ mà bạn nam thứ i muốn tặng hoa.

Output

Số bạn nam ít nhất cần lựa chọn

Example

Input:
3 3
1 2
2 3
1 3

Output:
2