#678. NYTRAVEL

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nguồn: Beginner Free Contest 16

Đất nước Free Contest đang trong quá trình xây dựng nên mạng lưới giao thông còn chưa hoàn thiện. Mạng lưới giao thông của đất nước này kết tối n thành phố bởi m con đường hai chiều.

Các thành số được đánh số từ 1 đến n . Đội tình nguyện viên của Free Contest đang ở thành phố 1 . Nhân dịp tết cổ truyền đang đến gần, đội tình nguyện viên muốn đi thăm nhiều thành phố nhất có thể. Nhưng vì mạng lưới giao thông chưa hoàn thiện, số thành phố các tình nguyện viên có thể thăm là khá ít. Họ quyết định xây thêm một con đường một chiều kết nối hai thành phố nào đó để tăng số lượng thành phố có thể đến thăm nhiều nhất có thể.

Tony nhận ra bài toán đếm số lượng tối đa thành phố có thể đến thăm sau khi xây dựng thêm một con đường rất thú vị, vì vậy anh ta quyết định đưa bài toán này vào contest sắp tới. Bạn sẽ giải quyết được bài toán này chứ?

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương n, m lần lượt là số lượng thành phố và số lượng con đường hai chiều trong mạng lưới giao thông (1 ≤ n, m ≤ 100000) ;
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v miêu tả rằng có một đường hai chiều kết nối giữa hai thành phố u v trong mạng lưới giao thông (u, v ≤ n) .

Dữ liệu ra:

  • Đưa ra một số nguyên duy nhất là số lượng thành phố tối đa đội tình nguyện viên có thể đến thăm.

Giới hạn:

  • 30\% số test ứng với 30\% số điểm có n ≤ 500 ;
  • 70\% số test còn lại không có giới hạn gì thêm.

Ví dụ:

Dữ liệu vào:
3 2
1 2
3 2
Dữ liệu ra:
3
Dữ liệu vào:
5 3
1 4
4 2
2 1
Dữ liệu ra:
4