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.|

BGTRAVEL - Đếm tour

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 ≤ 105; 1 ≤ m ≤ 2.105; k ≤ 105)
  • 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


Được gửi lên bởi:VOJ Team
Ngày:2015-12-09
Thời gian chạy:1s
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ừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Bắc Giang PreVOI 2015

hide comments
2019-08-27 19:19:08
ITK17 NBK đã xem :))
2019-04-29 07:18:48
1 đấm AC =)))))
2018-10-06 05:43:35
các fan hâm mộ của Cá Nóc Cắn Cáp điểm danh =)))
2018-10-06 04:48:33
https://bit.ly/2xZfITS
2018-09-06 03:30:41
solution+code: https://bit.ly/IEN3qB :))
2017-12-01 04:20:54
t là trungpro

Last edit: 2018-10-06 04:47:33
2017-12-01 04:20:31
cmt trc thằng bên trên
2017-12-01 04:18:07
second comment @zkg@
2017-12-01 04:17:15
first comment @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.