📘 Mô tả

Ở một vùng đồi núi, có n ngôi làng được nối với nhau bằng những con đường tạo thành một cây (giữa hai làng bất kỳ luôn có đúng một đường đi duy nhất).

Mỗi ngày, Trường và Lực đều đi từ một làng này sang một làng khác để thăm bạn bè. Cụ thể, có q kế hoạch đi chơi, mỗi kế hoạch gồm bốn ngôi làng u, v, x, y tương ứng với hành trình của Trường (từ u đến v) và Lực (từ x đến y).

Nhiệm vụ của bạn là xác định đoạn đường chung mà cả Trường và Lực đều đi qua trong ngày hôm đó. Nếu có, hãy in ra hai đầu mút a và b của đoạn đường giao nhau sao cho a ≤ b. Nếu không có đoạn nào trùng, in ra -1.

📥 Input

• Dòng đầu tiên chứa hai số nguyên n và q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵): số làng và số kế hoạch đi chơi.
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y: con đường nối hai ngôi làng.
• q dòng tiếp theo, mỗi dòng gồm bốn số nguyên u, v, x, y: mô tả hành trình của Trường và Lực.

📤 Output

Với mỗi kế hoạch, in ra hai số nguyên a và b đại diện cho đoạn đường chung giữa hành trình của Trường và Lực (thỏa a ≤ b), hoặc in -1 nếu không có đoạn nào chung.

🧪 Ví dụ

Input:

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

Output:

2 5 
-1