【题目描述】

给定一个二分图。左部包含 $n$ 个结点，编号从 $1$ 到 $n$，右部也包含 $n$ 个结点，编号从 $1$ 到 $n$。共有 $m$ 条边，每条边连接左部的一个结点和右部的一个结点。

你将被询问 $q$ 个独立的查询。在每个查询中，给定三个整数：$(a, b, k)$。

对于一个固定的查询 $(a, b, k)$，考虑在给定图上的以下过程。初始时，每个结点（包括左部和右部）的权重均为 $0$。你可以执行以下操作任意次：

• 选择左部结点的一个任意子集 $S$（可能为空），并选择一个正实数 $p > 0$。
• 令 $N(S)$ 为与 $S$ 中至少一个结点相邻的右部结点的集合。
• 将 $S$ 中每个结点的权重增加 $a \cdot p$。
• 将 $N(S)$ 中每个结点的权重增加 $b \cdot p$。

令 $p_1, p_2, \dots, p_{\ell}$ 为你在所有操作中使用的 $p$ 的值。这些值必须满足：

你的目标是选择这些操作（子集 $S$ 和值 $p$），使得所有结点（包括左部和右部）的权重总和最多为 $k$。在此约束下，你应该最大化左部所有结点的权重总和。

对于每个查询 $(a, b, k)$，每次都从所有结点权重为 $0$ 开始，计算可以获得的左部结点权重总和的最大可能值。

【输入格式】

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示子任务编号与测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含三个正整数 $n, m, q$。
• 接下来 $m$ 行每行两个整数 $u, v$，表示存在一条边，连接左部的第 $u$ 个点与右部的第 $v$ 个点。
• 接下来 $q$ 行每行三个整数 $a, b, k$，表示一个查询。

【输出格式】

对于每组测试数据的每个查询，输出一行一个实数表示左部点权重和的最大值。假设你的答案是 $a$，评测系统答案为 $b$，你的答案正确当且仅当 $\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$。

【样例 #0】

【输入】

0 2
5 8 3
1 2
1 3
2 4
2 5
3 1
3 3
4 2
5 4
1 3 5
2 1 2
5 2 3
2 3 3
1 2
1 1
2 1
1 0 2
0 2 2
3 1 4

【输出】

1.250000000000000
1.333333333333333
2.142857142857144
2.000000000000000
0.000000000000000
3.000000000000000

【数据范围】

记 $\sum n, \sum m, \sum q$ 表示一组测试点的所有数据中所有 $n, m, q$ 之和。

对于所有测试数据，保证：

• $1 \le t \le 1000$；
• $1 \le n \le 2000, \sum n \le 2000$；
• $1 \le m \le 10^4, \sum m \le 10^4$；
• $1 \le q \le 2 \cdot 10^5, \sum q \le 2 \cdot 10^5$；
• $1 \le u, v \le n$；
• $0 \le a, b \le 10^6$；
• $0 \le k \le 10^9$。
• 图中不存在重边。

特殊性质 A：每次询问的 $k \ge n \cdot (a+b)$。
特殊性质 B：每次询问的 $k = 1$。
特殊性质 C：一个右部点最多与一个左部点直接连接。
特殊性质 D：给出的二分图满足性质：存在最多 $5$ 个集合 $S$，使得只需对这些集合的部分操作，就能得到任意询问的最优解。注意这个限制针对的是二分图而非询问。