{"raw_statement":[{"iden":"statement","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"},{"iden":"входные данные","content":"В первой строке через пробел даны два целых числа 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. "},{"iden":"выходные данные","content":"Выведите одно число – ответ на вопрос задачи. Если проехать от жилого дома до центра эвакуации нельзя вовсе, выведите  - 1."},{"iden":"пример","content":"Входные данные6 81 2 31 3 21 4 41 6 52 3 153 6 83 5 74 5 11 5Выходные данные5"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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\\} $.","simple_statement":"You are given n parabolas, each defined by y = (x - a_i)² + b_i. These parabolas divide the plane into regions. Count how many regions have positive area.","has_page_source":false}