Condition Feasible Pairs in a Directed Acyclic Graph

We are given a rooted tree with \(n\) nodes (with the root being node \(1\)) where every edge is directed from a parent (shallower) to a child (deeper). In addition, \(m\) extra directed edges are added, and it is guaranteed that the final graph is still acyclic. In this graph:

• An event is represented by a node.
• An era is represented by a simple path.

A pair of events \((i,j)\) is said to be feasible if there exists a simple path from \(i\) to \(j\). However, Dream only cares about pairs which become connected because of the extra edges. Formally, a pair \((i,j)\) is conditionally feasible if and only if:

[ \text{(i,j) is feasible in the full graph,}\ \text{and not feasible in the original tree alone.} ]

Notice that in the tree (with only tree edges) there is a path from \(i\) to \(j\) exactly when \(i\) is an ancestor of \(j\). Thus a pair \((i,j)\) is conditionally feasible if:

[ \text{There exists a path from } i \text{ to } j \text{ in the DAG, but } i \text{ is not an ancestor of } j \text{ in the tree.} ]

You are given \(q\) queries. Each query is represented by two integers \(l\) and \(r\) (with \(l \le r\)). For each query, count the number of pairs \((i,j)\) with \(l \le i < j \le r\) that are conditionally feasible.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\).

The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing a tree edge directed from \(u\) (the parent) to \(v\) (the child).

The following \(m\) lines each contain two integers \(u\) and \(v\) representing an extra directed edge added to the tree.

The next \(q\) lines each contain two integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output one integer, the number of conditionally feasible pairs \((i,j)\) with \(l \le i < j \le r\).

sample

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

1
1