Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBFLOWER - Tặng hoa

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

Được gửi lên bởi:special_one
Ngày:2008-10-12
Thời gian chạy:0.206s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOICAMP

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.