BGTRAVEL - Đếm tour

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274766/problem/V

Một thành phố có n địa điểm du lịch đánh số từ 1 tới n và m con đường đánh số từ 1   tới

m. Con đường thứ i nối giữa hai điểm du lịch ui, ri  và cho phép đi lại giữa hai địa điểm  đó theo cả hai chiều. Hệ thống giao thông đảm bảo từ một điểm du lịch có thể đến   được

mọi điểm du lịch khác bằng những con đường đã cho, chú ý rằng giữa một cặp địa điểm có thể có nhiều con đường nối chúng.

Vào mùa du lịch, tắc đường trở thành vấn đề trầm trọng. Thông thường các lái xe khi  gặp đường tắc sẽ cố gắng chọn một đường khác để đi, nhưng trên thực tế có những con đường “độc đạo” không thể tránh khỏi. Một cách chính xác, mỗi con đường được gọi là độc đạo với hành trình s ⤳ t nếu mọi cách đi từ s tới t đều phải đi qua con đường  đó.

Việc tính toán ảnh hưởng của những con đường độc đạo sẽ giúp thành phố cải thiện hệ thống giao thông và việc của bạn chỉ cần trả lời một bài toán nhỏ:

Yêu cầu: Cho số nguyên k. Hãy cho biết có bao nhiêu cặp địa điểm (s, t) (s < t) mà mọi hành trình từ s tới t chắc chắn phải qua ít nhất k con đường độc đạo?

Input

  • Dòng 1 chứa ba số nguyên dương n, m, k (2 ≤ n ≤ 10 5 ; 1 ≤ m ≤ 2.10 5 ; k ≤ 10 5 )
  • m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương ui, ri  (ui   ≠  ri)
  • Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output

  • Một số nguyên duy nhất là kết quả tìm được

Example 

Input:





8 9 2






1 5






1 5






2 3






2 6






3 7






4 8






5 6






6 7






7 8






Output:
8

  • Người up: voj
  • Nguồn bài: Bắc Giang PreVOI 2015