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

Năm 2011, bạn quyết định đi du lịch qua một số thành phố của đất nước. Bạn sẽ xuất phát từ một thành phố bất kỳ, đi qua một số thành phố khác và trở về thành phố xuất phát. Bạn không muốn đi qua con đường nào 2 lần, nhưng một thành phố có thể được thăm nhiều lần tùy ý. Do năm 2011 là một năm lẻ, bạn muốn hành trình của mình đi qua một số lẻ các cạnh.

Cho bản đồ đất nước có dạng một đồ thị đơn vô hướng, bạn hãy tìm tất cả các thành phố có khả năng được đi qua trên hành trình của bạn.

Input

• Dòng đầu ghi 2 số N, M là số đỉnh và số cạnh của đồ thị. (1 <= N, M <= 100000)

• M dòng sau, mỗi dòng ghi 2 số u, v thể hiện một cạnh của đồ thị.

Output

• Ghi một số duy nhất là số lượng thành phố tìm được.

Giới hạn

• 50% số test có N <= 1000.

Example

Input:
6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

Output:
6