```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	head, to, nxt []int
	tot           int
	dfn, low, st  []int
	inSt          []bool
	timer         int
	scc           []int
	sccCnt        int
	level         []int
	sccNodes      [][]int
)

func addEdge(u, v int) {
	tot++
	to[tot] = v
	nxt[tot] = head[u]
	head[u] = tot
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func tarjan(u int) {
	timer++
	dfn[u] = timer
	low[u] = timer
	st = append(st, u)
	inSt[u] = true

	for i := head[u]; i > 0; i = nxt[i] {
		v := to[i]
		if dfn[v] == 0 {
			tarjan(v)
			low[u] = min(low[u], low[v])
		} else if inSt[v] {
			low[u] = min(low[u], dfn[v])
		}
	}

	if low[u] == dfn[u] {
		sccCnt++
		var comp []int
		for {
			v := st[len(st)-1]
			st = st[:len(st)-1]
			inSt[v] = false
			scc[v] = sccCnt
			comp = append(comp, v)
			if u == v {
				break
			}
		}
		sccNodes = append(sccNodes, comp)
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	var k int64
	fmt.Fscanf(reader, "%d %d %d\n", &n, &m, &k)

	head = make([]int, n+1)
	to = make([]int, m+1)
	nxt = make([]int, m+1)
	tot = 0

	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscanf(reader, "%d %d\n", &u, &v)
		addEdge(u, v)
	}

	dfn = make([]int, n+1)
	low = make([]int, n+1)
	scc = make([]int, n+1)
	inSt = make([]bool, n+1)
	sccNodes = make([][]int, 1) // 1-indexed for sccCnt

	for i := 1; i <= n; i++ {
		if dfn[i] == 0 {
			tarjan(i)
		}
	}

	level = make([]int, n+1)
	for i := 1; i <= n; i++ {
		level[i] = -1
	}

	ans := int64(0)

	for id := 1; id <= sccCnt; id++ {
		comp := sccNodes[id]
		if len(comp) == 1 {
			u := comp[0]
			hasSelfLoop := false
			for i := head[u]; i > 0; i = nxt[i] {
				if to[i] == u {
					hasSelfLoop = true
					break
				}
			}
			if !hasSelfLoop {
				continue
			}
		}

		start := comp[0]
		level[start] = 0
		q := []int{start}
		d := 0

		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			for i := head[u]; i > 0; i = nxt[i] {
				v := to[i]
				if scc[v] != id {
					continue
				}
				if level[v] == -1 {
					level[v] = level[u] + 1
					q = append(q, v)
				} else {
					diff := level[u] + 1 - level[v]
					if diff < 0 {
						diff = -diff
					}
					d = gcd(d, diff)
				}
			}
		}

		if d == 0 {
			continue
		}

		remK := int(k % int64(d))
		rem2K := int((2 * k) % int64(d))

		if rem2K != 0 {
			continue
		}

		counts := make([]int64, d)
		for _, u := range comp {
			counts[level[u]%d]++
		}

		if remK == 0 {
			ans += int64(len(comp))
			for i := 0; i < d; i++ {
				ans += counts[i] * (counts[i] - 1) / 2
			}
		} else {
			for i := 0; i < d/2; i++ {
				ans += counts[i] * counts[i+d/2]
			}
		}
	}

	fmt.Println(ans)
}
```