Phá hủy đường

Một đất nước có đúng $n$ thành phố, đánh số từ $1$ đến $n$, và $m$ con đường hai chiều nối các thành phố. Nếu hai thành phố $a$ và $b$ được nối bởi một con đường thì ta có thể đi từ $a$ sang $b$ hoặc từ $b$ sang $a$ trong đúng $1$ giờ. Mạng lưới đường ban đầu liên thông: từ thành phố bất kỳ đều đi được tới mọi thành phố khác.

Bạn muốn phá hủy càng nhiều con đường càng tốt, nhưng những con đường còn lại vẫn phải thỏa mãn đồng thời hai điều kiện:

• đi được từ $s_1$ tới $t_1$ trong không quá $l_1$ giờ;
• đi được từ $s_2$ tới $t_2$ trong không quá $l_2$ giờ.

Hãy xác định số con đường nhiều nhất có thể phá hủy. Nếu không thể đạt được cả hai điều kiện, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số thành phố và số con đường.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$, $b_i$ mô tả con đường nối hai thành phố $a_i$ và $b_i$.
• Dòng tiếp theo chứa ba số nguyên $s_1$, $t_1$, $l_1$.
• Dòng cuối chứa ba số nguyên $s_2$, $t_2$, $l_2$.

Dữ liệu ra

Một số nguyên duy nhất: số con đường nhiều nhất có thể phá hủy, hoặc $-1$ nếu không tồn tại phương án nào.

Ràng buộc

• $1\le n\le 3000$
• $0\le m\le min(3000,\frac{n(n-1)}{2})$
• $1\le a_i,b_i\le n$ và $a_i\ne b_i$
• Mỗi cặp thành phố được nối bởi nhiều nhất một con đường
• Mạng lưới đường ban đầu liên thông
• $1\le s_i,t_i\le n$ và $0\le l_i\le n$

Ví dụ