C. Медуза и EVA
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монстры снова вторглись в город! Асука приглашает свою хорошую подругу, Медузу, сесть за руль EVA вместе с ней.

В стране есть $$$n$$$ городов. Все монстры находятся в городе $$$n$$$. Медуза и Асука сейчас находятся в городе $$$1$$$ и должны переместиться в город $$$n$$$, чтобы победить монстров.

Существует $$$m$$$ дорог. По $$$i$$$-й дороге можно попасть из города $$$a_i$$$ в город $$$b_i$$$. Все дороги являются направленными. То есть из города $$$b_i$$$ в город $$$a_i$$$ по $$$i$$$-й дороге попасть нельзя. Интересно, что все дороги удовлетворяют условию $$$a_i<b_i$$$.

Вождение EVA требует совместной работы двух человек. Однако Асука и Медуза ранее не проводили совместных тренировок.

Предположим, что в данный момент EVA находится в городе $$$u$$$. Медуза и Асука выберут неразрушенную дорогу, которая начинается в городе $$$u$$$. Предположим, что Медуза и Асука выбирают дороги, которые заканчиваются в городах $$$v_1$$$ и $$$v_2$$$ соответственно. Если $$$v_1 = v_2$$$, то EVA успешно перемещается в город $$$v_1$$$. В противном случае EVA остается в городе $$$u$$$, а обе выбранные ими дороги будут уничтожены.

Возможна ситуация, когда EVA находится в городе $$$u$$$ ($$$u \neq n$$$) и нет неразрушенных дорог, начинающихся в городе $$$u$$$. В этом случае миссия будет провалена. А если в итоге они достигнут города $$$n$$$, то миссия будет считаться успешной.

Каждый раз, когда они выбирают дороги, Медуза знает, что Асука выберет дорогу случайным образом. Теперь Медуза хочет знать, если она выбирает дороги оптимально, то какова максимальная вероятность того, что миссия будет успешной.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке содержится количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 2000$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа, $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 5000$$$, $$$0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$$$) — количество городов и количество дорог.

В следующих $$$m$$$ строках каждого набора входных данных содержатся по два целых числа $$$a$$$ и $$$b$$$ ($$$1 \leq a < b \leq n$$$) — дорога из города $$$a$$$ в город $$$b$$$.

Гарантируется, что для каждого набора входных данных каждая дорога встречается не более одного раза.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$, а сумма $$$m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Выведите максимальную вероятность того, что миссия будет успешной, если Медуза выбирает дороги оптимально.

Ваш ответ будет принят, если абсолютная или относительная погрешность не превышает $$$10^{-9}$$$. Формально пусть ваш ответ равен $$$a$$$, а ответ жюри — $$$b$$$. Ваш ответ считается правильным, если $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$$$.

Пример
Входные данные
3
3 2
1 2
1 3
7 8
1 2
1 3
1 4
1 5
2 6
3 6
4 6
6 7
10 20
1 2
1 3
1 4
1 5
1 6
2 6
2 7
2 8
2 9
3 4
3 7
3 8
3 10
4 6
4 8
4 10
6 10
7 8
7 9
7 10
Выходные данные
0.500000000000
0.625000000000
0.491666666667
Примечание

В первом наборе входных данных Медуза выберет $$$v_1=3$$$, а Асука выберет $$$v_2=2$$$ с вероятностью $$$0.5$$$ и $$$v_2=3$$$ с вероятностью $$$0.5$$$. Миссия будет успешной с вероятностью $$$0.5$$$.