CF1874C Jellyfish and EVA

Monsters have invaded the town again! Asuka invites her good friend, Jellyfish, to drive EVA with her. There are $ n $ cities in the town. All the monsters are in city $ n $ . Jellyfish and Asuka are currently in city $ 1 $ and need to move to city $ n $ to defeat the monsters. There are $ m $ roads. The $ i $ -th road allows one to travel from city $ a_i $ to city $ b_i $ . All the roads are directed. That is, one cannot travel from city $ b_i $ to $ a_i $ using the $ i $ -th road. Interestingly, all roads satisfy $ a_i

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 2000 $ ). The description of the test cases follows. The first line of each test case contains two integers, $ n $ and $ m $ ( $ 2 \leq n \leq 5000 $ , $ 0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5) $ ) — the number of the cities and the number of the roads. In the following $ m $ lines of each test case, each line contains two integers $ a $ and $ b $ ( $ 1 \leq a < b \leq n $ ) — representing a road from city $ a $ to city $ b $ . It is guaranteed that for each test case, each road appears at most once. It is guaranteed that the sum of $ n $ over all test cases will not exceed $ 5000 $ and that the sum of $ m $ over all test cases will not exceed $ 2 \cdot 10^5 $ .

Output the maximum probability of the mission being successful if Jellyfish chooses the roads optimally. Your answer will be accepted if the absolute or relative error does not exceed $ 10^{-9} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is considered correct if $ \frac{|a-b|}{\max(1,|b|)} \leq 10^{-9} $ .

In the first test case, Jellyfish will choose $ v_1=3 $ , and Asuka will choose $ v_2=2 $ with a possibility of $ 0.5 $ and $ v_2=3 $ with a possibility of $ 0.5 $ . The mission is considered a success with a possibility of $ 0.5 $ .