Tý cần giải bài toán sau:

XOR đường đi

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Trong một thí nghiệm mật mã, người ta sử dụng \(N\) trạm phát tín hiệu được nối với nhau bởi \(N-1\) sợi cáp quang. Mỗi sợi cáp có một mã khóa là một số nguyên dương. Để mã hóa một thông điệp khi truyền từ trạm \(u\) đến trạm \(v\), người ta tính phép XOR (ký hiệu \(\oplus\)) của tất cả các mã khóa trên đường đi. Hãy giúp các nhà khoa học tính mã khóa tổng hợp cho mỗi đường truyền.

Yêu cầu: Cho \(N\) trạm và \(N-1\) sợi cáp. Trả lời \(Q\) truy vấn, mỗi truy vấn yêu cầu in ra XOR của các cạnh trên đường đi từ \(u\) đến \(v\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(N\).
• \(N-1\) dòng tiếp theo, mỗi dòng gồm ba số \(u\), \(v\), \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm hai số \(u\), \(v\).

Kết quả:

• In ra \(Q\) dòng, mỗi dòng là kết quả XOR của các cạnh trên đường đi.

Ví dụ:

Dữ liệu vào:

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

Kết quả:

4
6
3

Giải thích:

• Đường đi \(4 \to 2 \to 1 \to 3\): \(2 \oplus 3 \oplus 5 = 4\).
• Đường đi \(4 \to 2 \to 5\): \(2 \oplus 7 = 5\) (wait, 2 xor 7 = 5). Let me recompute: 4→2→5 = edge(4,2)=2, edge(2,5)=7 → 2 xor 7 = 5.
• Đường đi \(1 \to 2 \to 4\): \(3 \oplus 2 = 1\).

Wait, ví dụ trên chưa chính xác. Hãy thử với ví dụ đơn giản hơn:

Dữ liệu vào:

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

Kết quả:

6
3

Giải thích:

• Đường \(1 \to 2 \to 3\): \(3 \oplus 5 = 6\).
• Đường \(2 \to 1\): \(3\).

Giới hạn: | Subtask | \(N\) | \(Q\) | Điểm | |---------|-----|-----|------| | 1 | ≤ 100 | ≤ 100 | 5 | | 2 | ≤ 500 | ≤ 500 | 5 | | 3 | ≤ 2 000 | ≤ 2 000 | 10 | | 4 | ≤ 10 000 | ≤ 10 000 | 10 | | 5 | ≤ 50 000 | ≤ 50 000 | 15 | | 6 | ≤ 100 000 | ≤ 100 000 | 15 | | 7 | ≤ 100 000 | ≤ 100 000 | 20 | | 8 | ≤ 100 000 | ≤ 100 000 | 20 |