Triangular grid
The shaman puzzle-master Uanesmirtl drew numerous equilateral triangles on the ground (refer to the left illustration). He then selected a group of triangles that form a connected region by their sides (refer to the center illustration). Following this, he used a rope to outline a net consisting of all the boundaries of the selected triangles (refer to the right illustration).
You are provided with a detailed description of this net, along with two specific triangles chosen by Uanesmirtl. These triangles are identified by two sets of three nodes from the net, representing the vertices of each triangle. Your task is to determine the distance between these two triangles on Uanesmirtl's drawing. You can only move across the selected triangles, transitioning from one to another if they share a common side.
Input
The first line of the input contains two natural numbers, n and m (3 ≤ n, m ≤ 100000), representing the number of nodes and the segments of rope connecting neighboring nodes in the net tied by Uanesmirtl. It is guaranteed that this net corresponds to the boundaries of a connected set of triangles.
Each of the following m lines contains three numbers, indicating the nodes of the net connected by a segment of rope.
The next two lines each contain three numbers, specifying the nodes of the net that correspond to the vertices of the given triangles.
Output
Output the distance between the specified triangles on the initial drawing.