Nghiên cứu về ngoại hình sinh vật Z, các nhà khoa học quan tâm tới gen màu sắc và gen kích thước. Gen màu sắc có \(n_{1}\) trạng thái được đánh số thứ tự từ 1 tới \(n_{1}\), gen kích thước có \(n_{2}\) trạng thái được đánh số thứ tự từ 1 tới \(n_{2}\). Các nhà khoa học nhận thấy điều kì lạ là cứ sau mỗi giây thì sinh vật Z lại biến đổi cả về gen màu sắc lẫn gen kích thước, cụ thể:

• Có \(m_{1}\) khả năng về biến đổi gen màu sắc, mỗi khả năng ứng với 2 số nguyên \(u,\ v\ \left( 1 \leq u,v \leq n_{1} \right)\) (\(u,v\) không nhất thiết phân biệt) nếu sinh vật đang ở trạng thái gen màu sắc \(u\) sau 1 giây có thể chuyển sang trạng thái gen màu sắc \(v\) hoặc ngược lại đang ở trạng thái \(v\) có thể chuyển sang trạng thái \(u\). Giữa hai trạng thái gen màu sắc bất kì có thể biến đổi được sang nhau sau một thời gian nhất định.

• Có \(m_{2}\) khả năng về biến đổi gen kích thước, mỗi khả năng ứng với 2 số nguyên \(u,\ v\ \left( 1 \leq u,v \leq n_{2} \right)\) (\(u,v\) không nhất thiết phân biệt) nếu sinh vật đang ở trạng thái gen kích thước \(u\) sau 1 giây có thể chuyển sang trạng thái gen kích thước \(v\) hoặc ngược lại đang ở trạng thái \(v\) có thể chuyển sang trạng thái \(u\). Giữa hai trạng thái gen kích thước bất kì có thể biến đổi được sang nhau sau một thời gian nhất định.

Khi sinh vật Z đang ở trạng thái gen màu sắc \(x\ \left( 1 \leq x \leq n_{1} \right)\) và trạng thái gen kích thước \(y\ \left( 1 \leq y \leq n_{2} \right)\) thì gọi là ở trạng thái ngoại hình \((x,y)\).

Khi sinh vật Z đang ở trạng thái ngoại hình \((a,b)\), sau \(1\) giây có thể chuyển sang trạng thái ngoại hình \((c,\ d)\) nếu và chỉ nếu sau 1 giây có thể đồng thời chuyển từ trạng thái màu sắc \(a\) sang \(c\) và trạng thái kích thước \(b\) sang \(d.\)

Yêu cầu: Với mỗi trạng thái ngoại hình có thể đạt được nếu xuất phát ban đầu là trạng thái \((1,1)\), xác định lượng thời gian tối thiểu (giây) để đạt được trạng thái đó. Sau đó tính tổng của tất cả lượng thời gian tối thiểu xác định được.

Dữ liệu vào:

+ Dòng đầu chứa số nguyên \(n_{1},m_{1}\ \left( 1 \leq n_{1} \leq 40000;\ 1 \leq m_{1} \leq 100000 \right)\) là số trạng thái gen màu sắc và số khả năng biến đổi gen màu sắc;

+ \(m_{1}\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u,\ v\ \left( 1 \leq u,v \leq n_{1} \right)\) mô tả về một khả năng biến đổi trạng thái gen màu sắc;

+ Dòng tiếp theo chứa số nguyên \(n_{2},m_{2}\ \left( 1 \leq n_{2} \leq 40000;\ 1 \leq m_{2} \leq 100000 \right)\ \)là số trạng thái gen kích thước và số khả năng biến đổi gen kích thước;

+ \(m_{2}\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u,\ v\ \left( 1 \leq u,v \leq n_{2} \right)\) mô tả về một khả năng biến đổi trạng thái gen kích thước;

Kết quả:

+ Đưa ra một số nguyên là tổng của tất cả lượng thời gian tối thiểu xác định được chia dư cho \(10^{9} + 7\).

Ví dụ:

Giải thích:

Có tất cả 8 trạng thái ngoại hình, trong đó có 4 trạng thái có thể đạt được từ (1,1): trạng thái \((1,1)\) có thời gian tối thiểu là 0 giây, trạng thái \((2,\ 2),\ (2,\ 4)\ \) có thời gian tối thiểu 1 giây, trạng thái \((1,\ 3)\) có thời gian tối thiểu 2 giây, do đó đáp án là 4.

Ràng buộc:

• Ràng buộc 1: ứng với 40% số điểm có \(1 \leq n_{1},m_{1},\ n_{2},m_{2} \leq 200\);

• Ràng buộc 2: ứng với 40% số điểm có \(1 \leq n_{1},\ n_{2} \leq 3000;\ 1 \leq m_{1},m_{2} \leq 50000\);

• Ràng buộc 3: ứng với 20% số điểm có \(1 \leq n_{1},\ n_{2} \leq 40000;\ 1 \leq m_{1},m_{2} \leq 100000\);