Rhezo likes to play with graphs having N nodes and M edges. Lonewolf is ready to give him such a graph only on one condition. He wants Rhezo to find the number of critical links in the graph.

A critical link in a graph is an edge that has the following property: If we cut the link/edge, the graph will have exactly one more connected component than it previously had, and the difference between the number of nodes on each side of the edge is less than a certain integer P.

Given P and the graph, can you help Rhezo calculate the number of critical links?

Input:

First line contains 3 integers N, M and P as described in the problem statement. Each of the next M lines contain 2 integers A and B, meaning that node number A has a link/edge with node number B.

Output:

Find the number of critical links in the graph.

Constraints:

$1 \le N, M, P \le 10^{5}$

$1 \le A,B \le N$

$1 \le M \le max(10^{5},N \cdot (N-1) / 2)$