Шаман головоломок Уанесмиртль нарисовал на земле много равносторонних треугольников (см. рисунок слева), после чего выбрал некоторое количество треугольников, образующих связную по сторонам область (см. рисунок в центре). Затем он достал верёвку и связал сетку, которая состоит из всех границ выбранных треугольников (см. рисунок справа).
Вам дано подробное описание сетки, и заданы два треугольника из выбранных Уанесмиртлем - даны две тройки узлов сетки, соответствующие вершинам этих треугольников. Найдите расстояние от одного треугольника до другого на рисунке Уанесмиртля, если передвигаться можно только по выбранным им треугольникам, переходя с одного на другой, если у них есть общая сторона.
Первая строка входного файла содержит натуральные числа n и m (3 ≤ n, m ≤ 100000) - количество узлов и отрезков верёвки, соединяющих соседние узлы, в сетке, связанной Уанесмиртлем. Гарантируется, что эта сетка соответствует множеству границ некоторого связного набора треугольников.
Каждая из следующих m строк содержит три числа - номера узлов сетки, связанных отрезком верёвки.
В последующих двух строках содержаться по три числа - номера узлов сетки, соответствующих вершинам заданных треугольников.
Выведите расстояние между заданными треугольниками на изначальном рисунке.