eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Трикутна сітка

Трикутна сітка

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Шаман ломиголовок Уанесміртль накреслив на землі багато рівносторонніх трикутників (див. рисунок ліворуч), після чого вибрав деяку кількість трикутників, які утворюють звязну по сторонам область (див. рисунок у центрі). Потім він дістав мотузку і звязав сітку, яка складається з усіх границь вибраних трикутників (див. рисунок праворуч).

Вам задано детальний опис сітки, і задано два трикутники із вибраних Уанесміртлем - задано дві трійки вузлів сітки, які відповідають вершинам цих трикутників. Знайдіть відстань від одного трикутника до іншого на рисунку Уанесміртля, якщо пересуватись можна лише по вибраним ним трикутникам, переходячи з одного на інший, якщо у них є спільна сторона.

Вхідні дані

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

Кожен з наступних m рядків містить три числа - номери вузлів сітки, зв'язаних відрізком мотузки.

У наступних двох рядках міститься по три числа - номери вузлів сітки, відповідних вершинам заданих трикутників.

Вихідні дані

Виведіть відстань між заданими трикутниками на початковому рисунку.

Приклад

Вхідні дані #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
Вихідні дані #1
4