Among the many delicacies of Minas Gerais, cheese and doce de leite are the most famous. Although both are made from the same raw material, milk, their production and storage processes are quite different. In particular, all the cheese in the state is produced in city $$$A_1$$$ and stored in city $$$A_2$$$, while all the doce de leite is produced in city $$$B_1$$$ and stored in city $$$B_2$$$. To move the stocks from one city to another, each product is transported along some of the $$$M$$$ two-way roads, each of which connects exactly two of the $$$N$$$ cities in Minas Gerais.
Besides their culinary importance, cheese and doce de leite are fundamental to the state's political and social stability: a shortage of both delicacies, even for a short time, is enough to turn our characteristic hospitality into deep animosity. Concerned about this possibility, the Movement of Minas Pacifists (MMP) needs to know: what is the minimum number of roads that, if closed, would make it impossible to transport the cheese from $$$A_1$$$ to $$$A_2$$$ and the doce de leite from $$$B_1$$$ to $$$B_2$$$? Write a program to help the MMP find this answer.
The first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$4 \leq N \leq 2000$$$, $$$0 \leq M \leq 2000$$$), indicating the number of cities and roads in Minas Gerais, respectively.
Each of the next $$$M$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$, $$$u \neq v$$$), indicating that there is a road between cities $$$u$$$ and $$$v$$$. It is guaranteed that there is at most one road between the same pair of cities.
After these $$$M$$$ lines, there is one last line containing four distinct integers $$$A_1$$$, $$$A_2$$$, $$$B_1$$$, and $$$B_2$$$, indicating the production and storage cities of the cheese and the doce de leite, respectively.
The output should contain a single integer, indicating the minimum size of a set of roads that, after being closed, makes both transports impossible.
6 51 32 33 44 54 61 5 2 6
1
6 41 22 34 55 61 3 4 6
2
5 41 33 43 51 51 2 4 5
1
Explanation for example 1
In this example, if the road connecting cities $$$3$$$ and $$$4$$$ is closed, there will no longer be a path between cities $$$1$$$ and $$$5$$$, nor between cities $$$2$$$ and $$$6$$$.
Explanation for example 2
In this example, if the roads between $$$1$$$ and $$$2$$$, and between $$$4$$$ and $$$5$$$, are closed, this would prevent both the existence of a path between $$$1$$$ and $$$3$$$ and of a path from $$$4$$$ to $$$6$$$. It can be proven that this is the minimum number of roads that must be closed for this to happen.
Explanation for example 3
In this example, it is already impossible to go from city $$$1$$$ to city $$$2$$$. Therefore, if the road from $$$3$$$ to $$$4$$$ is closed, it becomes impossible both to go from $$$1$$$ to $$$2$$$ and to go from $$$4$$$ to $$$5$$$.
