{"problem":{"name":"G. Водный мир","description":{"content":"Шел 2567 год. Глобальное потепление привело к таянию полярного льда и практически вся поверхность Земли оказалась затоплена. Однако человечество не погибло. Ученые изобрели новые способы строительства","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10144G"},"statements":[{"statement_type":"Markdown","content":"Шел 2567 год. Глобальное потепление привело к таянию полярного льда и практически вся поверхность Земли оказалась затоплена. Однако человечество не погибло. Ученые изобрели новые способы строительства городов. \n\nЗдания представляют собой высокие каменные столбы, частично погруженные в воду. Некоторые здания соединены друг с другом мостом, который расположен на определенной высоте. Мост соединяет здания в двух направлениях. Первый этаж каждого здания находится на уровне воды. Каждое здание включает в себя этажи с 1 по 109. Заметим, что два здания могут быть соединены двумя и более мостами, которые расположены на разных высотах. Два здания, например, могут быть соединены тремя мостами, которые расположены на высотах 7, 119 и 4432. \n\nОднако жители города обеспокоены тем, что уровень воды продолжает подниматься. Они хотят знать, при каком максимальном уровне воды можно добраться от жилого дома A до центра эвакуации B. \n\nВаша задача – ответить на вопрос жителей. Заметим, что если вода находится на уровне некоторого моста, то по нему все еще можно перемещаться.\n\nВ первой строке через пробел даны два целых числа 2 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105 – количество зданий и мостов. \n\nВ следующих m строках через пробел даны по три целых числа a, b, c, которые задают описание мостов. Первые два числа это номера зданий, которые соединяет мост, 1 ≤ a,  b ≤ n, a ≠ b. Третье число – высота, на которой расположен мост 1 ≤ c ≤ 109. \n\nВ последней строке через пробел даны два числа A и B – номер жилого дома и номер центра эвакуации, 1 ≤ A,  B ≤ n, A ≠ B. \n\nВыведите одно число – ответ на вопрос задачи. Если проехать от жилого дома до центра эвакуации нельзя вовсе, выведите  - 1.\n\n## Входные Данные\n\nВ первой строке через пробел даны два целых числа 2 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105 – количество зданий и мостов. В следующих m строках через пробел даны по три целых числа a, b, c, которые задают описание мостов. Первые два числа это номера зданий, которые соединяет мост, 1 ≤ a,  b ≤ n, a ≠ b. Третье число – высота, на которой расположен мост 1 ≤ c ≤ 109. В последней строке через пробел даны два числа A и B – номер жилого дома и номер центра эвакуации, 1 ≤ A,  B ≤ n, A ≠ B. \n\n## Выходные Данные\n\nВыведите одно число – ответ на вопрос задачи. Если проехать от жилого дома до центра эвакуации нельзя вовсе, выведите  - 1.\n\n## Пример\n\nВходные данные6 81 2 31 3 21 4 41 6 52 3 153 6 83 5 74 5 11 5Выходные данные5\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of parabolas.  \nFor each $ i \\in \\{1, \\dots, n\\} $, define the parabola $ P_i $ by the equation:  \n$$ y = (x - a_i)^2 + b_i $$  \nwhere $ a_i, b_i \\in \\mathbb{Z} $, $ |a_i| \\leq 10^9 $, $ |b_i| \\leq 10^9 $.\n\n**Constraints**  \n$ 1 \\leq n \\leq 1000 $\n\n**Objective**  \nCompute the number of connected regions (faces) of positive area into which the plane is divided by the arrangement of the $ n $ parabolas $ \\{P_1, \\dots, P_n\\} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10144G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}