In some country there are exactly *n* cities and *m* bidirectional roads connecting the cities. Cities are numbered with integers from 1 to *n*. If cities *a* and *b* are connected by a road, then in an hour you can go along this road either from city *a* to city *b*, or from city *b* to city *a*. The road network is such that from any city you can get to any other one by moving along the roads.

You want to destroy the largest possible number of roads in the country so that the remaining roads would allow you to get from city *s*<sub class="lower-index">1</sub> to city *t*<sub class="lower-index">1</sub> in at most *l*<sub class="lower-index">1</sub> hours and get from city *s*<sub class="lower-index">2</sub> to city *t*<sub class="lower-index">2</sub> in at most *l*<sub class="lower-index">2</sub> hours.

Determine what maximum number of roads you need to destroy in order to meet the condition of your plan. If it is impossible to reach the desired result, print -1.
The first line contains two integers *n*, *m* (1 ≤ *n* ≤ 3000, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b430c1611da69c57f92e1c1fb5b38b5aae0f93cb.png" style="max-width: 100.0%;max-height: 100.0%;"/>) — the number of cities and roads in the country, respectively. 

Next *m* lines contain the descriptions of the roads as pairs of integers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>). It is guaranteed that the roads that are given in the description can transport you from any city to any other one. It is guaranteed that each pair of cities has at most one road between them.

The last two lines contains three integers each, *s*<sub class="lower-index">1</sub>, *t*<sub class="lower-index">1</sub>, *l*<sub class="lower-index">1</sub> and *s*<sub class="lower-index">2</sub>, *t*<sub class="lower-index">2</sub>, *l*<sub class="lower-index">2</sub>, respectively (1 ≤ *s*<sub class="lower-index">*i*</sub>, *t*<sub class="lower-index">*i*</sub> ≤ *n*, 0 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *n*).
# region My classes and methods
import copy
from collections import deque


class Queue:
    def __init__(self):
        self.items = deque([])
        self.visited = False

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.items:
            return self.items.popleft()

    def size(self):
        return len(self.items)


class City:
    def __init__(self, number):
        self.name = number
        self.adyacents = []


def citybfs(cityQ, distances, paths):
    while cityQ.size() != 0:
        itemcity = cityQ.dequeue()
        for otheritemcity in itemcity.adyacents:
            if distances[otheritemcity.name] == -1:
                distances[otheritemcity.name] = distances[itemcity.name] + 1
                paths[otheritemcity.name] = itemcity
                cityQ.enqueue(otheritemcity)


def citys_to_cityt(fullpath, path, citys, cityt):
    if path:
        if cityt == citys:
            path.insert(0, citiesList[citys])
            return
        path.insert(0, citiesList[cityt])
        cityt = fullpath[cityt].name
        return citys_to_cityt(fullpath, path, citys, cityt)
    else:
        path.append(citiesList[cityt])
        cityt = fullpath[cityt].name
        return citys_to_cityt(fullpath, path, citys, cityt)
    # endregion


print("Number of cities and roads:")
NandM = input().split(" ")
NumCities = int(NandM[0])
NumRoads = int(NandM[1])
print("Write the ", NumRoads, " roads:")

'''
This was the implementation of graphs by array, but in the end is a bit faster
make a linked list of cities. 
GraphCity = []
for i in range(NumCities):
    GraphCity.append([])
    for j in range(NumCities):
        GraphCity[i][j].append(0)

for i in range(NumRoads):
    templist = input().split(" ")
    GraphCity[templist[0]][templist[1]] = 1;
'''
citiesList = []
for i in range(NumCities):
    citiesList.append(City(i))

for i in range(NumRoads):
    templist = input().split(" ")
    if citiesList[int(templist[1]) - 1] not in citiesList[int(templist[0]) - 1].adyacents:
        citiesList[int(templist[0]) - 1].adyacents.append(citiesList[int(templist[1]) - 1])
    if citiesList[int(templist[0]) - 1] not in citiesList[int(templist[1]) - 1].adyacents:
        citiesList[int(templist[1]) - 1].adyacents.append(citiesList[int(templist[0]) - 1])

print("Introduce starting city #1, finishing city #1 and max travel time #1")
stl1 = input().split(" ")
citys1 = int(stl1[0]) - 1
cityt1 = int(stl1[1]) - 1
time1 = int(stl1[2])

print("Introduce starting city #2, finishing city #2 and max travel time #2")
stl2 = input().split(" ")
citys2 = int(stl2[0]) - 1
cityt2 = int(stl2[1]) - 1
time2 = int(stl2[2])

firstPathVert = []
firstDistances = []
firstPath = []
for i in range(NumCities):
    firstDistances.append(- 1)
    firstPath.append(0)
firstDistances[citys1] = 0
firstPath[citys1] = -1
firstQ = Queue()
firstQ.enqueue(citiesList[citys1])
citybfs(firstQ, firstDistances, firstPath)
# for i in range(firstPath):
#   if i == 0 :

secondDistances = []
secondPath = []
for i in range(NumCities):
    secondDistances.append(-1)
    secondPath.append(0)
secondDistances[citys2] = 0
secondPath[citys2] = -1
secondQ = Queue()
secondQ.enqueue((citiesList[citys2]))
citybfs(secondQ, secondDistances, secondPath)

if firstDistances[cityt1] > time1 or secondDistances[cityt2] > time2:
    print("-1")
    exit(0)
MultPathBeg = False
firstPathbegin = False
secondPathbegin = False
firstPathend = False
secondPathend = False
fullfirst = []

fullsecond = []
citys_to_cityt(firstPath, fullfirst, citys1, cityt1)
citys_to_cityt(secondPath, fullsecond, citys2, cityt2)
setfirst = set(copy.copy(fullfirst))
setsecond = set(copy.copy(fullsecond))

if setfirst.isdisjoint(setsecond):
    print(NumCities - len(fullfirst) - len(fullsecond) - 2)
    exit(0)

CommonPathbeg = -1
CommonPathends = -1
CommonSet = setfirst.intersection(setsecond)
commonIndex = []

for i in range(len(fullfirst)):
    if fullfirst[i] in CommonSet:
        commonIndex.append(fullfirst[i])

# Finding the distances between the first common vertice and the cities
DistanceFirsttoi = firstDistances[commonIndex[0].name]
DistanceSecondtoi = secondDistances[commonIndex[0].name]

''''
distanceFirsttoI = []
PathFirsttoI = []
for i in range(NumCities):
    distanceFirsttoI.append(-1)
    PathFirsttoI.append(0)
distanceFirsttoI[citys1] = 0
PathFirsttoI[citys1] = -1
NewQ1 = Queue()
NewQ1.enqueue((citiesList[citys1]))
citybfs(NewQ1, distanceFirsttoI, PathFirsttoI)
DistanceFirsttoi = distanceFirsttoI[commonIndex[0].name]

distanceSecondtoI = []
PathSecondtoI = []
for i in range(NumCities):
    distanceSecondtoI.append(-1)
    PathSecondtoI.append(0)
distanceSecondtoI[citys1] = 0
PathSecondtoI[citys1] = -1
NewQ1 = Queue()
NewQ1.enqueue((citiesList[citys1]))
citybfs(NewQ1, distanceSecondtoI, PathSecondtoI)
DistanceSecondtoi = distanceFirsttoI[commonIndex[0].name]
'''

# Finding distances between the first and the last common vertices
Distanceitoj = firstDistances[commonIndex[len(commonIndex) - 1].name] - firstDistances[commonIndex[0].name]

# Finding distances between the last common vertices and the last vertices
FirstDistancejtolast = firstDistances[cityt1] - firstDistances[commonIndex[len(commonIndex) - 1].name]
SecondDistancejtolast = secondDistances[cityt2] - secondDistances[commonIndex[len(commonIndex) - 1].name]

print(NumRoads - DistanceFirsttoi - DistanceSecondtoi - Distanceitoj - FirstDistancejtolast - SecondDistancejtolast)
