Sau khi hòa nhịp được với "Trái Tim Hổ Phách", các phong ấn bảo vệ Cung Điện Hổ Phách dần được gỡ bỏ. Tuy nhiên, lối lên ngai vàng của vua KDA – đỉnh tháp cao nhất "The Zenith" – đã bị vỡ vụn thành hàng ngàn mảnh lơ lửng trong không trung.

Không gian tại đây bị bẻ cong, các quy tắc vật lý thông thường không còn áp dụng. Để di chuyển, các bạn tìm thấy một bảo vật do chính tay nhà vua chế tác năm xưa: Khối Lập Phương Hư Không.

Khu vực này được mô tả như một bản đồ các mảnh vỡ không gian gồm ~N~ mảnh (đánh số từ ~1~ đến ~N~). Vị trí hiện tại của các bạn là mảnh số ~1~, và đích đến là ngai vàng tại mảnh số ~N~. Các mảnh vỡ được kết nối với nhau bởi ~M~ luồng năng lượng. Khoảng cách giữa hai mảnh vỡ bất kỳ được tính bằng số bước ngắn nhất đi theo các luồng năng lượng này.

Khối Lập Phương Hư Không hoạt động theo cơ chế rủi ro nhưng đầy quyền năng:

1. Nạp năng lượng: Mỗi lần muốn di chuyển, bạn phải kích hoạt khối lập phương. Nó có ~K~ mức năng lượng từ ~1~ đến ~K~. Xác suất để khối lập phương đạt mức năng lượng ~x~ là ~P_x~.
2. Ổn định không gian: Tuy nhiên, năng lượng không gian rất bất ổn. Nếu khối lập phương đạt mức năng lượng là ~x~, thực tế nó sẽ chỉ cho phép bạn thực hiện bước nhảy với khoảng cách ~y~ (~1 \le y \le x~) với một xác suất là ~G_{x, y}~.
3. Chọn điểm đến: Khi khoảng cách nhảy ~y~ đã được ấn định bởi vũ trụ, bạn có quyền năng tự chọn điểm đến tiếp theo là bất kỳ mảnh vỡ nào cách vị trí hiện tại đúng một khoảng bằng ~y~.

Quy Tắc "Lực Hút Ngai Vàng": Nếu khoảng cách nhảy ~y~ đủ lớn để bạn chạm tới hoặc vượt qua ngai vàng (khoảng cách từ chỗ đứng đến đích ~\le y~), bạn sẽ ngay lập tức được dịch chuyển thẳng đến ngai vàng và kết thúc hành trình.

Vì vua KDA sắp trở nên hoá điên nên thời gian không còn nhiều, Nhà hiền triết muốn tính toán chiến thuật di chuyển tối ưu để số lần kích hoạt Khối Lập Phương trung bình là thấp nhất.

Input

Dòng đầu tiên chứa ~1~ số nguyên dương ~T~ (~T \le 10~) là số lượng tình huống giả lập ta cần xử lý.

Trong mỗi tình huống có:

• Dòng đầu tiên chứa ~3~ số nguyên dương ~N, M, K~ ~(N \le 10^5, M \le 5 \cdot 10^5, K \le 100)~.
• Dòng tiếp theo chứa ~K~ số nguyên ~P'_1, P'_2, \dots, P'_K~ ~(1 \le P'_i \le 100, \sum_{i = 1}^K P'_i = 100, 100 * P_i = P'_i)~.
• ~K~ dòng tiếp theo được đánh số từ ~1~ đến ~K~, dòng thứ ~i~ chứa ~i~ số nguyên không âm ~G'_{i, 1}, G'_{2, i}, \dots, G'_{i, i}~ ~(0 \le G'_{i, x} \le 100, \sum_{j = 1}^K G'_{i, j} = 100, 100 * G_{i, x} = G'_{i, x})~.
• Trong mỗi dòng của ~M~ dòng tiếp theo chứa ~2~ số nguyên dương ~u, v~ là ~2~ mảnh vỡ được kết nối với nhau bởi ~1~ luồng năng lượng ~(u, v \le N)~.

* Lưu ý: Đề đảm bảo tổng số mảnh vỡ ~N~ không vượt quá ~10^5~ cũng như tổng số luồng năng lượng ~M~ không vượt quá ~5 \cdot 10^5~ trong tất cả các tình huống.

Output

Với mỗi tình huống, in ra trên một dòng là một số thực ~D~ là đáp án của đó tình huống đó (đáp án được coi là đúng nếu sai số không quá ~10^{-6}~).

In ra ~D = 0~ trong trường hợp bạn không đến được mảnh vỡ thứ ~N~.

2
4 3 3
20 30 50
100
0 100
0 0 100
1 2
2 3
3 4
5 5 10
10 10 10 10 10 10 10 10 10 10
100
10 90
10 10 80
10 10 10 70
10 10 10 10 60
10 10 10 10 10 50
10 10 10 10 10 10 40
10 10 10 10 10 10 10 30
10 10 10 10 10 10 10 10 20
10 10 10 10 10 10 10 10 10 10
1 2
1 3
1 4
1 5
4 5

1.5400000000
1.0000000000

Đề không văn

Cho ~1~ đồ thị ~G = (V, E)~ với ~N = |V|~ và ~M = |E|~. Các đỉnh trong đồ thị được đánh số từ ~1~ đến ~N~. Cho thêm ~1~ xúc xắc có ~K~ mặt được đánh số bằng số nút, và mỗi mặt ~x~ có xác xuất tung là ~P_x~. Gọi ~d(x, y)~ là hàm tính khoảng cách ngắn nhất đi từ đỉnh ~x~ đến đỉnh ~y~ tình bằng cạnh.

Hiện tại ta đang ở đỉnh ~1~ của đồ thị và đang tìm cách đến đỉnh ~N~, nhưng để làm được thì trước khi di chuyển ta phải tung xúc xắc. Giả sử đỉnh ta đang ở là ~s~, thì khi tung ra mặt ~x~ của xúc xắc, ta có thể đến ~1~ trong số những đỉnh ~t~ thỏa ~d(s, t) \le x~. Đặc biệt, ta có ~G_{x, y}~ phần trăm khả năng chọn đến ~1~ trong những đỉnh ~t~ thỏa ~d(s, t) = y~ (tất nhiên ~y \le x~) khi tung được số nút là ~x~. Ta sẽ lặp lại bước tung xúc xắc, chọn đỉnh muốn đến tại mỗi lượt di chuyển cho đến khi đến được đỉnh ~N~. Đặc biệt nếu ta chọn nhảy khoảng cách ~y~ mà ta đã có thể đến đỉnh ~N~ với khoảng cách ngắn hơn thì ta được mặc định là đã đến đỉnh ~N~.

Yêu cầu: Tìm số lượt trung bình ít nhất ta cần để di chuyển từ đỉnh ~1~ đến ~N~.

Input

Dòng đầu tiên chứa ~1~ số nguyên dương ~T~ (~T \le 10~) là số testcase ta phải xử lý.

Trong mỗi testcase có:

• Dòng đầu tiên chứa ~3~ số nguyên dương ~N, M, K~ ~(N \le 10^5, M \le 5 \cdot 10^5, K \le 100)~.

• Dòng tiếp theo chứa ~K~ số nguyên ~P'_1, P'_2, \dots, P'_K~ ~(1 \le P'_i \le 100, \sum_{i = 1}^K P'_i = 100, 100 * P_i = P'_i)~.

• ~K~ dòng tiếp theo được đánh số từ ~1~ đến ~K~, dòng thứ ~i~ chứa ~i~ số nguyên không âm ~G'_{i, 1}, G'_{2, i}, \dots, G'_{i, i}~ ~(0 \le G'_{i, x} \le 100, \sum_{j = 1}^K G'_{i, j} = 100, 100 * G_{i, x} = G'_{i, x})~.

• Trong mỗi dòng của ~M~ dòng tiếp theo chứa ~2~ số nguyên dương ~u, v~ là ~2~ đỉnh của ~1~ cạnh trong đồ thị ~(u, v \le N)~.

* Lưu ý: Đề đảm bảo tổng số đỉnh ~N~ không vượt quá ~10^5~ cũng như tổng số cạnh ~M~ không vượt quá ~5 \cdot 10^5~ trong tất cả các testcase.

Output

Với mỗi testcase, in ra trên ~1~ dòng là ~1~ số thực ~D~ là đáp án của testcase đó (đáp án được coi là đúng nếu sai số không quá ~10^{-6}~).

Sample Input 1

2
4 3 3
20 30 50
100
0 100
0 0 100
1 2
2 3
3 4
5 5 10
10 10 10 10 10 10 10 10 10 10
100
10 90
10 10 80
10 10 10 70
10 10 10 10 60
10 10 10 10 10 50
10 10 10 10 10 10 40
10 10 10 10 10 10 10 30
10 10 10 10 10 10 10 10 20
10 10 10 10 10 10 10 10 10 10
1 2
1 3
1 4
1 5
4 5

Sample Output 1

1.5400000000
1.0000000000