N. Traveling - Du lịch

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: Trình chấm ngoài

Đề bài

Hè năm nay, lớp 11 Tin tổ chức đi du lịch. Mạng lưới các thành phố là một đồ thị vô hướng gồm n đỉnh (tương ứng với n thành phố) đánh số từ 1 đến n . Có m tuyến đường hai chiều nối trực tiếp giữa các cặp thành phố. Hãy cho biết, nếu xuất phát từ thành phố Sơn La là thành phố 1 , có thể thăm được những thành phố nào (chỉ đi qua hệ thống các đường như trên).

Dữ liệu:

  • Dòng đầu chứa hai số nguyên dương n, m\ (1 \le n, m \le 10^5) ;
  • m dòng tiếp theo, mỗi dòng chứa hai số u, v cho biết có đường hai chiều nối trực tiếp giữa hai thành phố u v (1\le u, v \le n, u\ne v) .

Kết quả:

  • Ghi ra một số nguyên duy nhất là số thành phố thăm được (tính cả thành phố 1 ).

Ví dụ:

Dữ liệu:

6 6
1 2
2 3
3 1
3 5
4 6
5 2

Kết quả:

4

Giải thích:

  • Từ thành phố 1 đi thăm được 4 thành phố gồm: 1, 2, 3, 5 .

Giới hạn:

  • Subtask \#1: 80\% số điểm có 1\le n \le 1000 ;
  • Subtask \#2: 20\% số điểm còn lại có 1000 < n \le 10^5 .