Монстры снова вторглись в город! Асука приглашает свою хорошую подругу, Медузу, сесть за руль 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\), то миссия будет считаться успешной.
Каждый раз, когда они выбирают дороги, Медуза знает, что Асука выберет дорогу случайным образом. Теперь Медуза хочет знать, если она выбирает дороги оптимально, то какова максимальная вероятность того, что миссия будет успешной.
Выходные данные
Выведите максимальную вероятность того, что миссия будет успешной, если Медуза выбирает дороги оптимально.
Ваш ответ будет принят, если абсолютная или относительная погрешность не превышает \(10^{-9}\). Формально пусть ваш ответ равен \(a\), а ответ жюри — \(b\). Ваш ответ считается правильным, если \(\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}\).