Xe bus

Thành phố Alpha có \(n\) địa điểm đánh số \(1, 2, 3, \ldots, n\) với \(n - 1\) con đường hai chiều đảm bảo kết nối giữa tất cả các địa điểm. Con đường thứ \(i\) kết nối trực tiếp giữa hai địa điểm \(u_i\) và \(v_i\).

Có \(m\) tuyến xe bus với các số hiệu lần lượt \(1, 2, 3, \ldots, m\). Tuyến xe thứ \(j\) (\(1 \le j \le m\)) di chuyển hai chiều theo lộ trình bắt đầu từ địa điểm \(p_j\), đi qua các địa điểm không lặp lại và kết thúc tại địa điểm \(q_j\).

Yêu cầu: Với mỗi địa điểm, xác định tuyến xe bus có số hiệu nhỏ nhất đi qua địa điểm đó.

Input

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\).

• \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) xác định con đường thứ \(i\).

• Dòng tiếp theo chứa số nguyên dương \(m\).

• \(m\) dòng cuối cùng, dòng thứ \(j\) (\(1 \le j \le m\)) chứa hai số \(p_j\) và \(q_j\) xác định thông tin tuyến xe bus thứ \(j\) (\(1 \le p_j, q_j \le n\); \(p_j \ne q_j\)).

Ràng buộc: Gọi \(T_j\) là số đỉnh trên đường đi từ \(p_j\) tới \(q_j\). Đặt \(S = T_1 + T_2 + T_3 + \ldots + T_m\).

• Subtask 1 (khoảng \(17\%\) số điểm): \(n, m \le 1000\), \(u_i = i\), \(v_i = i + 1\) với mọi \(i = 1, 2, 3, \ldots, n - 1\).

• Subtask 2 (khoảng \(17\%\) số điểm): \(n \le 1000\), \(m = 1\).

• Subtask 3 (khoảng \(16\%\) số điểm): \(n, m \le 1000\).

• Subtask 4 (khoảng \(17\%\) số điểm): \(n \le 3 \times 10^5\); \(m \le 2 \times 10^5\); \(S \le 5 \times 10^6\).

• Subtask 5 (khoảng \(33\%\) số điểm): \(n \le 3 \times 10^5\); \(m \le 2 \times 10^5\).

Output

In ra \(n\) dòng, dòng thứ \(i\) chứa số nguyên \(c_i\) xác định tuyến xe bus có số hiệu nhỏ nhất đi qua địa điểm thứ \(i\) (\(1 \le i \le n\)). Trường hợp địa điểm \(i\) không có tuyến xe bus nào đi qua thì \(c_i = -1\).

Example

Input:

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

Output:

1
-1
3
2
3
1
1

Note

• Tuyến xe thứ nhất đi qua các điểm \(1, 6, 7\). Ta có \(c_1 = c_6 = c_7 = 1\).

• Tuyến xe thứ hai đi qua các điểm \(7, 6, 4\). Ta có \(c_4 = 2\).

• Tuyến xe thứ ba đi qua các điểm \(3, 1, 6, 7, 5\). Ta có \(c_3 = c_5 = 3\).

• Địa điểm \(2\) không có tuyến xe nào chạy qua. \(c_2 = -1\).