Maintenance Plan on Tree Roads

Country \(A\) is an ancient nation with \(n\) cities numbered from \(1\) to \(n\). City \(1\) is the capital and the only city with a port. Imported goods are brought in at the capital and then transported to other cities.

The king of \(A\) decides to build several one‐way roads exclusively for transporting goods. Ministers propose a plan with \(m\) one–way roads such that, using these roads, one can reach every city from the capital. Moreover, the network of these \(m\) roads is acyclic.

Due to financial constraints, the king will initially build only \(n-1\) of these roads in order to guarantee basic connectivity. He selects the \(n-1\) roads by a procedure similar to a depth-first search (DFS) as follows:

1. Let the set \(S\) initially contain only the capital (city \(1\)) and set the current city \(u=1\).
2. If there is an outgoing road from \(u\) to a city \(v\) not in \(S\), choose the one with the smallest city number, mark that road as a priority road, add \(v\) to \(S\), and set \(u\) as the parent of \(v\).
3. Then update \(u\) to \(v\). If \(u\) has multiple choices, always pick the smallest; if there is no available \(v\), backtrack by setting \(u\) to its parent.
4. Repeat until all cities have been added to \(S\).

The \(n-1\) selected priority roads form a tree (called the tree roads) with the capital as the root. Later, as the whole network of \(m\) roads is built, these tree roads (often older) require maintenance.

The ministers propose \(q\) maintenance plans. In each plan, for two cities \(a\) and \(b\) (with \(a\) being an ancestor of \(b\) in the DFS tree), all tree roads on the unique path between \(a\) and \(b\) will be under maintenance (and thus disabled). This may disconnect parts of the tree. The king wishes to know, for each plan, when the tree roads between \(a\) and \(b\) are disabled, how many cities in the subtree of \(b\) become unreachable from the capital.

Note: Even though the tree roads are disabled, the other non–tree roads remain available. Thus, some cities in \(b\)'s subtree may still be reachable via an alternative path in the overall road network.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) (the number of cities, the number of roads, and the number of queries, respectively).

Then \(m\) lines follow, each with two integers \(u\) and \(v\) indicating a one–way road from city \(u\) to city \(v\). It is guaranteed that using the \(m\) roads one can reach every city from the capital \(1\) and that the \(m\) roads form a directed acyclic graph.

Then \(q\) lines follow, each containing two integers \(a\) and \(b\) (with \(a\) being an ancestor of \(b\) in the DFS tree constructed by the procedure above), representing a maintenance plan.

outputFormat

For each maintenance plan, output a single integer on a separate line — the number of cities in the subtree of \(b\) (in the DFS tree) that become unreachable from the capital when all tree roads on the path between \(a\) and \(b\) are disabled.

sample

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

0
1
0