Cho đồ thị ~n~ đỉnh được đánh số từ ~1~ đến ~n~ và ~m~ cạnh. Cạnh thứ ~i~ nối hai đỉnh ~u_i, v_i~. Đồ thị đảm bảo luôn có đường đi giữa hai đỉnh bất kì và giữa hai đỉnh có thể có nhiều cạnh nối giữa chúng.

Đường đi từ ~a~ đến ~b~ được biểu diễn bằng dãy các đỉnh ~a = x_1 x_2 ... x_p=b~, với ~1 \le x_i \le n~, ~(x_i, x_{i + 1})~ là một cạnh của đồ thị. Cạnh ~(x_i, x_{i + 1})~ được gọi là cạnh đặc biệt trên đường đi từ ~a~ đến ~b~ nếu mọi đường đi từ ~a~ đến ~b~ phải qua cạnh ~(x_i, x_{i + 1})~.

Yêu cầu: Cho số nguyên ~k~. Tính số lượng cặp đỉnh ~(a, b)~ ~(a < b)~ sao cho mọi đường đi từ ~a~ đến ~b~ đi qua ít nhất ~k~ cạnh đặc biệt.

Input

Dòng thứ nhất chứa ba số nguyên ~n, m, k~ ~(2 \le n \le 10^5, 1 \le m \le 2 \times 10^5, k \le 10^5)~.

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i, v_i~ ~(u_i \neq v_i)~.

Output

Số lượng cặp đỉnh ~(a, b)~ ~(a < b)~ sao cho mọi đường đi từ ~a~ đến ~b~ qua ít nhất ~k~ cạnh đặc biệt.

Subtasks

Subtask 1 (~70 \%~ số điểm): ~n \le 100~.

Subtask 2 (~30 \%~ số điểm): Không có ràng buộc nào thêm.

Sample Input

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

Sample Output

1