Tô màu đường đi

Taki có một cây gồm \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Ban đầu, tất cả các cạnh đều được tô màu \(0\).

Anh ấy sẽ thực hiện \(k\) thao tác. Trong thao tác thứ \(i\), Taki chọn hai đỉnh \(x_i\) và \(y_i\), sau đó tô tất cả các cạnh trên đường đi ngắn nhất từ \(x_i\) đến \(y_i\) bằng màu \(i\). Nếu một cạnh đã được tô màu trước đó, màu mới sẽ ghi đè lên màu cũ.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((2 \leq n \leq 5 \times 10^5,\ 1 \leq k \leq 5 \times 10^5)\) --- số đỉnh của cây và số màu.
• Mỗi dòng trong \(n - 1\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i, v_i \leq n)\) --- biểu thị cạnh thứ \(i\) nối hai đỉnh \(u_i\) và \(v_i\). Đảm bảo rằng các cạnh tạo thành một cây.
• Mỗi dòng trong \(k\) dòng tiếp theo chứa hai số nguyên \(x_i\) và \(y_i\) \((1 \leq x_i, y_i \leq n)\) --- mô tả thao tác tô màu đường đi từ đỉnh \(x_i\) đến \(y_i\) bằng màu \(i\).

Output

Gọi \(d(i)\) là màu cuối cùng của cạnh thứ \(i\) theo thứ tự xuất hiện của input.
In ra \(\prod \max(d(i), 1)\) \(mod\) \((10^9+7)\)

Example

6 2
1 2
2 3
2 4
1 5
4 6
5 2
6 1

8

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

48

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 20 & \(n, k \leq 2000\)

2 & 25 & \(u_i = i\), \(v_i = i + 1\) với mọi \(i\)

3 & 20 & \(n, k \leq 10^5\)

4 & 35 & Không có ràng buộc bổ sung

\hline
\endtabular