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