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\) (\(1 \leq u, v \leq n_1\)) (\(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.
• 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\) (\(1 \leq u, v \leq n_2\)) (\(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.

Giữa hai trạng thái 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\) (\(1 \leq x \leq n_1\)) và trạng thái gen kích thước \(y\) (\(1 \leq y \leq n_2\)), 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\) (\(1 \leq n_1 \leq 40000\); \(1 \leq m_1 \leq 100000\)) 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\) (\(1 \leq u, v \leq n_1\)) 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\) (\(1 \leq n_2 \leq 40000\); \(1 \leq m_2 \leq 100000\)) 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\) (\(1 \leq u, v \leq n_2\)) mô tả về một khả năng biến đổi trạng thái gen kích thước.

Dữ liệu ra:

• Đư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\).

Input 1

2 1
1 2
4 4
1 2
2 3
3 4
4 1

Output 1

4

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 \le n_1, m_1, n_2, m_2 \le 200;\)
• Ràng buộc 2: ứng với 40% số điểm có \(1 \le n_1, n_2 \le 3000;\) \(1 \le m_1, m_2 \le 50000;\)
• Ràng buộc 3: ứng với 20% số điểm có \(1 \le n_1, n_2 \le 40000;\) \(1 \le m_1, m_2 \le 100000;\)