Distinct Paths Stamina Cost

Alice and Marisa live in a huge forest consisting of \(N\) intersections and \(M\) directed paths. Marisa loves visiting Alice, but Alice dislikes her. Being very observant, Alice will not answer the door if she recognizes that Marisa has used a route that is exactly the same as one she used before. In order to eventually convince Alice to answer, Marisa decides to use a new (i.e. distinct) path each time she visits.

Marisa has limited stamina. She will only use paths that consist of at most \(K\) edges. Moreover, if she reaches Alice's house using exactly \(t\) edges (with \(0 \le t \le K\)), she spends \(t^2\) units of her stamina. Marisa wonders: if she continues visiting until there is no new path (of no more than \(K\) edges) available, how much total stamina will she spend?

The forest is represented as a directed graph. You are given \(Q\) queries. In each query, you are given two nodes \(S\) and \(T\); if Marisa's house is at \(S\) and Alice's house is at \(T\), compute the total stamina cost incurred when Marisa has exhausted all distinct paths from \(S\) to \(T\) whose number of edges is between 0 and \(K\) (inclusive).

Path Definition:

A path is defined as a sequence of \(P\) edges \(A_{m_0},A_{m_1}, \ldots, A_{m_{P-1}}\) (with \(P\) being any nonnegative integer) such that for each \(1 \le i < P\), the ending node of \(A_{m_{i-1}}\) is the starting node of \(A_{m_i}\). Two paths are considered identical if they have the same length \(P\) and for every index \(0 \le i < P\), the \(i^{th}\) edge is the same in both paths.

inputFormat

The first line of input contains three integers \(N\), \(M\), and \(K\) \((1 \leq N, M, K \leq \text{reasonable limits})\), representing the number of intersections, the number of directed paths, and the maximum number of edges Marisa is willing to walk, respectively.

The next \(M\) lines each contain two integers \(u\) and \(v\), indicating a directed edge from node \(u\) to node \(v\).

The following line contains an integer \(Q\), the number of queries.

Each of the next \(Q\) lines contains two integers \(S\) and \(T\), representing the starting intersection (Marisa's house) and the target intersection (Alice's house).

outputFormat

For each query, output a single integer on a new line — the total stamina cost Marisa will spend, where each distinct path from \(S\) to \(T\) of length \(t\) (with \(t \leq K\)) contributes \(t^2\) to the total.

sample

3 3 3
1 2
2 3
1 3
2
1 3
2 3

5
1