Description

  歷史課有好幾條規定,稱不上是不合理,但很惱人。這也讓歷史課成為班上學生不怎麼喜歡的課程之一。
- 不可以使用 3C 產品
- 不可以睡覺
- 吃飯要去教室外面吃
- 不可以比老師晚到,遲到要在黑板上畫圈圈並記上時間
- 要做一些報告,通常需要花好幾個小時

然而,這並不影響歷史這一科其實很有趣的事實,如果不考試的話。除了推敲每個時期發生了什麼,以及它為什麼發生,學習歷史中我們常常可以發現一些很好玩的巧合:
- 牛津大學在宋朝就成立了
- 慈禧太后大概用的是愛迪生公司的供電系統和燈泡
- 麥當勞在二戰期間創立

你會發現,這種通常平常不會想到的巧合正是因為我們缺乏橫向連結。所以,我們給定很多事件,希望求所有事件到彼此之間最短的時間差。

  然而,哆拉A夢在這時候出現了並拿出了如果電話亭。
  「如果,這世界上的加法全部變成乘法...」
  「啊啊啊不行!會壞掉的!啊啊啊!」

  然而,在撥打完後,因為本身的運算也從加法變成乘法了,所以哆拉A夢和如果電話亭都壞掉了。你知道,如果要將哆拉A夢和如果電話亭修好就必須要讓事件之間產生連結。一般來說需要耗用大量能量,而耗用能量最少的辦法...

  「不就是我們剛剛做的所有事件彼此之間最短的時間距離嗎?」

  然而,並沒有這麼簡單,因為年份也變得混亂,所以我們能得到的只有兩個事件之間的評估值。而更遠的點之間的評估值,我們用一連串的評估值相乘得到,例如:

A-5-B-2-C

AB 之間評估值為 5, BC 之間評估值 2,則 AC 間的評估值為 $5 \times 2 = 10$。而如果有多條可能路徑,我們取最小值。例如:

A-5-B-2-C
|       |
----7----

AC 之間評估值為 7。

  你可以幫幫他們,把哆啦A夢修好嗎?

Input Format

第一行有兩個數 $N, M, Q$ ,代表有 $N$ 個編號 $1$~$N$ 的事件和 $M$ 條事件之間的評估值與 $Q$ 筆詢問。
接下來有 M 行,每行有三個數 $u, v, w$ ,分別代表編號 $u, v$ 之間的評估值為 $w$
接下來有 $Q$ 行,每行有二個數 $u, v$,請輸出u到v的最短距離的以十為底的對數,即$log_{10}(dis(u,v))$

$N \le 1500$
$M \le 3000$
$Q \le 100000$
$1 \le u,v \le N$
$1 \le w \le 10{18}$
保證圖連通

Output Format

對於每次詢問,請輸出$log_{10}(dis(u,v))$
輸出的答案與真正的答案絕對誤差在 $10 ^ {-6}$ 內皆視為正確

Sample Input 1

3 3 1
1 2 5
2 3 2
1 3 7
1 3

Sample Output 1

0.845098040014256813

Sample Input 2

4 4 3
1 2 1
1 3 100
2 3 100
3 4 10000
2 3
1 4
2 4

Sample Output 2

2
6
6

Hints

Problem Source

TopCoder

AaW
學弟電爛我了

User's AC Ratio

100.0% (1/1)

Tags

Problem Setter

Subtasks

No. Testdata Range Constraints Score
1 0~9 $n \le 20, m\le 100,q \le 100, w=10$ 10
2 10~19 $n\le 500, m\le 1000, q \le 10000$ 20
3 20~29 $w=10 ^ x, 0\le x\le 18$ 20
4 0~39 無其他限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 4
1 1000 262144 65536 1 4
2 1000 262144 65536 1 4
3 1000 262144 65536 1 4
4 1000 262144 65536 1 4
5 1000 262144 65536 1 4
6 1000 262144 65536 1 4
7 1000 262144 65536 1 4
8 1000 262144 65536 1 4
9 1000 262144 65536 1 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 2 4
14 1000 262144 65536 2 4
15 1000 262144 65536 2 4
16 1000 262144 65536 2 4
17 1000 262144 65536 2 4
18 1000 262144 65536 2 4
19 1000 262144 65536 2 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 3 4
29 1000 262144 65536 3 4
30 1000 262144 65536 4
31 1000 262144 65536 4
32 1000 262144 65536 4
33 1000 262144 65536 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
38 1000 262144 65536 4
39 1000 262144 65536 4