I. MST Queries
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected, undirected, weighted graph with $$$n$$$ vertices and $$$m$$$ edges labeled from $$$1$$$ through $$$m$$$. Define:

  • $$$G[l, r]$$$: the graph on all $$$n$$$ vertices containing only the edges numbered from $$$l$$$ to $$$r$$$.
  • $$$\text{W}(H)$$$: the total weight of a minimum spanning tree$$$^{[7]}$$$ of graph $$$H$$$, or $$$\infty$$$ in case $$$H$$$ is disconnected.

You have to process $$$q$$$ queries. For each query specified by a range $$$[l, r]$$$, count the number of pairs $$$(x, y)$$$ that satisfy the following:

  • $$$l \leq x \leq y \leq r$$$;
  • $$$\text{W}(G[x, y]) = \text{W}(G[1, m])$$$.
Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — denoting the number of vertices, the number of edges, and the number of queries.

The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$1 \leq w_i \leq 10^9$$$) — representing the edges of the graph. It is guaranteed that the given edges form a connected graph. Note that the graph may contain self-loops and multiple edges.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le m$$$).

Output

For each query, output a single integer — the number of valid pairs $$$(x, y)$$$.

Example
Input
4 6 3
1 4 20
1 2 10
2 3 20
3 4 5
1 3 15
2 4 25
1 6
2 5
1 5
Output
4
1
2