Məsələlər
Треугольная сетка
Треугольная сетка
Шаман головоломок Уанесмиртль нарисовал на земле много равносторонних треугольников (см. рисунок слева), после чего выбрал некоторое количество треугольников, образующих связную по сторонам область (см. рисунок в центре). Затем он достал верёвку и связал сетку, которая состоит из всех границ выбранных треугольников (см. рисунок справа).
\includegraphics{https://static.e-olymp.com/content/f8/f897a144d9fabde1355cdea9726ec7b9cc5fdd44.jpg}
Вам дано подробное описание сетки, и заданы два треугольника из выбранных Уанесмиртлем - даны две тройки узлов сетки, соответствующие вершинам этих треугольников. Найдите расстояние от одного треугольника до другого на рисунке Уанесмиртля, если передвигаться можно только по выбранным им треугольникам, переходя с одного на другой, если у них есть общая сторона.
\InputFile
Первая строка входного файла содержит натуральные числа \textbf{n} и \textbf{m} (\textbf{3} ≤ \textbf{n}, \textbf{m} ≤ \textbf{100000}) - количество узлов и отрезков верёвки, соединяющих соседние узлы, в сетке, связанной Уанесмиртлем. Гарантируется, что эта сетка соответствует множеству границ некоторого связного набора треугольников.
Каждая из следующих \textbf{m} строк содержит три числа - номера узлов сетки, связанных отрезком верёвки.
В последующих двух строках содержаться по три числа - номера узлов сетки, соответствующих вершинам заданных треугольников.
\OutputFile
Выведите расстояние между заданными треугольниками на изначальном рисунке.
Giriş verilənləri #1
7 11 1 2 1 3 1 4 1 5 1 6 1 7 2 3 3 4 4 5 5 6 6 7 1 2 3 1 6 7
Çıxış verilənləri #1
4