Наводнение
Мы все знаем, что король Тритон нас недолюбливает, и поэтому случаются кораблекрушения, ураганы и цунами. Но, устав от однообразия, Тритон решил устроить в этом году грандиозное наводнение.
Он выбрал небольшой городок в холмистой долине недалеко от моря. Силы Тритона достаточно, чтобы пролить один сильный дождь на холм. Однако он беспокоится, что вода может не достичь выбранного города из-за различных речных бассейнов и потоков воды. Тритон просит вас помочь ему рассчитать количество воды, которое достигнет выбранного города.
На пути к городу в холмистой долине находятся водоемы. Некоторые из них соединены друг с другом реками. Если какой-то водоем переполнен водой, вода начинает равномерно течь в соединенные водоемы (или в море, если соединенных водоемов нет). Каждый водоем изначально содержит некоторое количество воды, и также известна его максимальная вместимость. Выбранный город расположен на берегу одного из водоемов — вам нужно рассчитать уровень воды в этом водоеме после того, как весь поток воды иссякнет.
Входные данные
В первой строке входных данных даны целые числа N и K (2 ≤ N ≤ 10^4, 0 ≤ K ≤ 10^5) — количество водоемов и количество соединений между водоемами соответственно.
В следующих N строках входных данных даны целые числа P_i и A_i (0 ≤ A_i ≤ P_i ≤ 10^6) — это максимальная вместимость i-го водоема и его начальный уровень воды.
В следующих K строках входных данных даны целые числа F_j и T_j (1 ≤ F_j, T_j ≤ N, F_j ≠ T_j) — они обозначают возможное речное соединение от водоема F_j к водоему T_j (обратный поток воды невозможен). Считайте, что поток воды из водоема равномерно распределяется между всеми возможными соединениями потока из этого водоема. Тритон абсолютно уверен, что между водоемами нет циклов в речных потоках, и между любыми двумя водоемами нет нескольких рек.
В последней строке входных данных даны целые числа X, Y и Z (1 ≤ X, Z ≤ N, 1 ≤ Y ≤ 10^6) — водоем, который получает сильный дождь от Тритона, количество воды, добавляемое в этот водоем, и целевой водоем (рядом с выбранным городом) для проверки соответственно.
Считайте, что избыточная вода вытекает из водоема, только если его вместимость полна. Если какой-то водоем переполнен и из него не определены потоки воды, считайте, что вся избыточная вода вытекла в море.
Выходные данные
Первая строка вывода должна содержать одно число с плавающей точкой L_z — конечный уровень воды в целевом водоеме, когда весь поток воды завершен. Ответы с абсолютной или относительной ошибкой менее 10^{-4} считаются правильными.