Ngưỡng Liên Thông

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh có trọng số. Với một ngưỡng $W$, ta chỉ giữ những cạnh có trọng số không vượt quá $W$.

Mỗi truy vấn cho hai đỉnh khác nhau $x$ và $y$. Hãy tìm giá trị nhỏ nhất $W$ để $x$ và $y$ liên thông trong đồ thị được giữ lại. Khi tồn tại giá trị đó, gọi $S$ là số đỉnh trong thành phần liên thông chứa $x$ và $y$ sau khi tất cả cạnh có trọng số không vượt $W$ đã được thêm; hãy in cả $W$ và $S$.

Nhiều cạnh có thể có cùng trọng số. Vì vậy, kích thước $S$ luôn được xác định sau khi xử lý trọn vẹn nhóm cạnh có trọng số $W$, không phụ thuộc thứ tự các cạnh trong nhóm.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa $u,v,w$ mô tả cạnh vô hướng giữa $u$ và $v$ có trọng số $w$.
• Dòng tiếp theo chứa số truy vấn $q$.
• $q$ dòng cuối, mỗi dòng chứa hai đỉnh $x$ và $y$ khác nhau.

Output

• Với mỗi truy vấn, nếu hai đỉnh không thể liên thông thì in $-1$; ngược lại in hai số $W$ và $S$, trong đó $W$ là ngưỡng nhỏ nhất và $S$ là kích thước thành phần sau khi thêm tất cả cạnh có trọng số không vượt $W$.

Constraints

• $1\le n,m,q\le 10^5$.
• $1\le u,v,x,y\le n$; $u\ne v$ và $x\ne y$.
• $1\le w\le 10^9$.
• Đồ thị có thể có nhiều cạnh cùng trọng số và không nhất thiết liên thông.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

7 4
10 6
2 2
10 6
-1