小明國(guó)慶節(jié)準(zhǔn)備去某星系進(jìn)行星際旅行，這個(gè)星系里一共有 n 個(gè)星球，其中布置了 m 道雙向傳送門，第 i 道傳送門可以連接 ai，bi 兩顆星球（ai , bi 且任意兩顆星球之間最多只有一個(gè)傳送門）。
他看中了一款 “旅游盲盒”，一共有 Q 個(gè)盲盒，第 i 個(gè)盲盒里的旅行方案規(guī)定了旅行的起始星球 xi 和最多可以使用傳送門的次數(shù) yi。只要從起始星球出發(fā)，使用傳送門不超過(guò)規(guī)定次數(shù)能到達(dá)的所有星球都可以去旅行。
小明關(guān)心在每個(gè)方案中有多少個(gè)星球可以旅行到。小明只能在這些盲盒里隨機(jī)選一個(gè)購(gòu)買，他想知道能旅行到的不同星球的數(shù)量的期望是多少。
輸入共 m + Q + 1 行。
第一行為三個(gè)正整數(shù) n，m，Q。
后面 m 行，每行兩個(gè)正整數(shù) ai，bi。
后面 Q 行，每行兩個(gè)整數(shù) xi，yi。
3 2 3 1 2 2 3 2 1 2 0 1 1
2.00
【樣例說(shuō)明】
第一個(gè)盲盒可以旅行到 1, 2, 3。
第二個(gè)盲盒可以旅行到 2。
第三個(gè)盲盒可以旅行到 1, 2。
所以期望是 (3 + 1 + 2)/3 = 2.00。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 20% 的評(píng)測(cè)用例，保證 n ≤ 300。
對(duì)于 100% 的評(píng)測(cè)用例，保證 n ≤ 1000，m ≤ min{n(n?1)/2, 5n}，Q ≤ 50000，0 ≤ yi ≤ n。