H. Racsó's Toy Train
time limit per test
2.6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Racsó has a toy train that he loves. It has $$$n$$$ numbered stations joined by $$$m$$$ bidirectional track segments. Initially, the train can travel from any station to any other.

Two distinct stations are well connected if, after any track segment comes loose, the train can still travel between those two stations. Only one segment comes loose at a time.

Miguel wants to make the train more reliable. For each of $$$q$$$ plans he can add two colored track segments: one between stations $$$a$$$ and $$$b$$$, and another between stations $$$c$$$ and $$$d$$$.

For each plan, count the unordered pairs of distinct stations that satisfy the following three conditions:

  • They are well connected if both new segments are added.
  • They are not well connected if only the segment between $$$a$$$ and $$$b$$$ is added.
  • They are not well connected if only the segment between $$$c$$$ and $$$d$$$ is added.

In each scenario, the segment that comes loose can be any of those that exist in it, including the two new ones.

The plans are independent: each one starts from Racsó's original train and no new segment is kept for the next plan.

A new segment may join the same stations as an original track or as the other proposed segment. They are different physical tracks: if one comes loose, the others keep working. The four stations of a plan do not have to be distinct.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$2 \leq n \leq 2 \times 10^{5}$$$, $$$n - 1 \leq m \leq 3 \times 10^{5}$$$, $$$1 \leq q \leq 2 \times 10^{5}$$$).

The next $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), the endpoints of an original segment. The train is connected and does not contain two original segments with the same endpoints.

The next $$$q$$$ lines contain four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$1 \leq a, b, c, d \leq n$$$, $$$a \neq b$$$, $$$c \neq d$$$), describing a plan with two new segments.

Output

Print $$$q$$$ lines. On each line, print the number of pairs corresponding to that plan. Each pair is counted only once, regardless of the order of its stations.

Examples
Input
4 3 5
1 2
2 3
3 4
1 3 2 4
1 2 2 3
1 2 3 4
1 4 2 3
1 3 3 4
Output
1
1
0
0
2
Input
5 4 1
1 2
1 3
1 4
1 5
2 3 4 5
Output
4
Note

Explanation for example 1

In the first plan, the only pair that needs both new segments is $$$\{1,4\}$$$. With only the first one, the train depends on segment $$$3\text{-}4$$$; with only the second one, it depends on $$$1\text{-}2$$$.

In the second plan, additional copies of segments $$$1\text{-}2$$$ and $$$2\text{-}3$$$ are added. The pair $$$\{1,3\}$$$ becomes well connected only when both copies are added.

In the last plan, the pairs that satisfy the conditions are $$$\{1,4\}$$$ and $$$\{2,4\}$$$.

Explanation for example 2

The pairs are $$$\{2,4\}$$$, $$$\{2,5\}$$$, $$$\{3,4\}$$$ and $$$\{3,5\}$$$. The alternative routes of the train are allowed to pass through the same station: being well connected refers to a loose segment, not to a closed station.