Dù nghe đến cửa hàng kem Bedao đã lâu, ông thị trưởng thành phố VNOI vẫn chưa có thời gian để thưởng thức món kem *Bīngqílín 2023. May mắn thay, một trong những kế hoạch đầu năm mới 2023 chính là cải thiện giao thông trong thành phố, và ông thị trưởng muốn nhân cợ hội này có thể tiết kiệm được thời gian đi lại của bản thân (cũng như tất cả mọi người).

Thành phố VNOI có ~n~ nút giao thông được đánh số từ ~1~ đến ~n~, và có ~m~ đường đi hai chiều nối các nút giao thông. Tất cả các đường đi đều có độ dài bằng ~1~. Giữa hai nút giao thông có tối đa một đường đi nối chúng, và không có con đường nào nối một nút giao thông với chính nó. Từ một nút giao thông có thể đi đến mọi nút giao thông khác thông qua các con đường trong thành phố. Được biết rằng thị trưởng làm việc ở tòa nhà gần nút giao thông ~1~, và cửa hàng kem Bedao nằm ở nút giao thông ~n~.

Trong kế hoạch cải thiện giao thông lần này, thành phố sẽ xây thêm một con đường nối giữa hai nút giao thông khác nhau mà chưa có đường đi trực tiếp nào giữa chúng trước đó. Con đường này do ông thị trưởng trực tiếp chọn xây dựng, do đó ông thị trưởng muốn rằng đường đi ngắn nhất từ nơi mình làm việc đến cửa hàng kem Bedao có độ dài chính xác là ~k~, để khi từ cửa hàng kem Bedao đến nơi làm việc, thời gian di chuyển là tối ưu nhất, xong ông vẫn có thể thưởng thức Bīngqílín 2023 trên đường đi làm của mình.

Cho danh sách đường đi của thành phố và số ~k~ mà ông thị trưởng chọn. Hãy giúp ông thị trưởng đếm xem có bao nhiêu cách xây con đường mới thỏa mãn yêu cầu của ông.

Hai cách xây đường là khác nhau nếu chúng nối hai nút giao thông khác nhau.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~ (~1 \le n, m, k \le 500\,000~, ~m < \frac{n \times (n - 1)}{2}~)  – số lượng nút giao thông trong thành phố, số lượng con đường đã xây trong thành phố, và số ~k~ mà ông thị trưởng đã chọn.

Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~u~ và ~v~ (~1 \le u, v \le n~, ~u \ne v~) thể hiện có một con đường nối nút giao thông thứ ~u~ và ~v~.

Dữ liệu đảm bảo rằng giữa hai nút giao thông có không quá một đường đi nối chúng, không có con đường nào nối cùng một nút giao thông, và từ một nút giao thông có thể đi đến mọi nút giao thông khác trong thành phố thông qua các con đường trong thành phố.

Output

In ra một số nguyên duy nhất là số lượng cách xây dựng con đường mới khác nhau thỏa mãn yêu cầu của ông thị trưởng.

Scoring

• Subtask 1 (~450~ điểm): ~n, m \le 500~.

• Subtask 2 (~600~ điểm): ~n, m \le 5000~.

• Subtask 3 (~450~ điểm): không có ràng buộc gì thêm.

Tổng cộng bài toán có ~1500~ điểm.

Sample Input

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

Sample Output

4

Notes

Có ~4~ cách xây dựng con đường mới là: ~(1, 5)~, ~(1, 4)~, ~(2, 6)~ và ~(3, 6)~.