Tỉnh ZZZ có ~N~ thành phố, được đánh số từ ~0~ đến ~N-1~, và ~N-1~ con đường hai chiều. Từ mỗi thành phố luôn có thể đi đến mọi thành phố khác bằng một dãy các con đường. Khoảng cách giữa hai thành phố là số con đường ít nhất cần đi qua để di chuyển từ thành phố này đến thành phố kia.

Hai cán bộ Nam và Huy cần thực hiện một chuyến tuần tra toàn tỉnh. Ban đầu Nam đứng ở thành phố ~X~, Huy đứng ở thành phố ~Y~. Mỗi ngày, đúng một trong hai người di chuyển từ thành phố hiện tại sang một thành phố kề với nó qua một con đường. Chuyến tuần tra kết thúc khi cả Nam và Huy đều đã từng đến tất cả các thành phố ít nhất một lần và cả hai quay lại đúng thành phố xuất phát của mình.

Độ an toàn của một chuyến tuần tra là khoảng cách nhỏ nhất giữa Nam và Huy trong suốt chuyến đi, tính cả thời điểm ban đầu và các thời điểm sau mỗi lần di chuyển. Với mỗi truy vấn ~(X,Y)~, hãy tìm độ an toàn lớn nhất có thể đạt được nếu Nam bắt đầu ở ~X~ và Huy bắt đầu ở ~Y~.

Input

• Dòng đầu tiên chứa ba số nguyên ~S, N~ và ~Q~ ~(1 \le S \le 5, 1 \le N \le 2 \cdot 10^5, 1 \le Q \le 10^5)~: chỉ số subtask của test, số thành phố và số truy vấn.

• Trong ~N-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~A_i~ và ~B_i~ ~(0 \le A_i,B_i < N)~, mô tả một con đường nối hai thành phố ~A_i~ và ~B_i~.

• Trong ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X~ và ~Y~ ~(0 \le X,Y < N)~, mô tả một truy vấn.

Dữ liệu đảm bảo các con đường tạo thành một cây.

Output

In ra ~Q~ dòng. Dòng thứ ~j~ chứa một số nguyên là độ an toàn lớn nhất cho truy vấn thứ ~j~.

Scoring

Sample Input 1

1 13 5
0 1
1 2
2 3
0 4
4 5
5 6
0 7
7 8
8 9
0 10
10 11
11 12
3 6
3 2
1 10
12 9
0 3

Sample Output 1

3
1
2
3
3

Notes

Xét truy vấn đầu tiên ~(3,6)~. Một cách đạt độ an toàn ~3~ là cho hai người luân phiên đứng chờ ở một lá của cây, còn người kia đi từ lá hiện tại qua thành phố ~0~ sang một lá thuộc nhánh khác. Cụ thể, có thể thực hiện lần lượt các đoạn sau:

• Nam đi ~3 \rightarrow 9~, Huy đứng tại ~6~.

• Huy đi ~6 \rightarrow 12~, Nam đứng tại ~9~.

• Nam đi ~9 \rightarrow 6~, Huy đứng tại ~12~.

• Huy đi ~12 \rightarrow 3~, Nam đứng tại ~6~.

• Nam đi ~6 \rightarrow 12~, Huy đứng tại ~3~.

• Huy đi ~3 \rightarrow 9~, Nam đứng tại ~12~.

• Nam đi ~12 \rightarrow 3~, Huy đứng tại ~9~.

• Huy đi ~9 \rightarrow 6~, Nam đứng tại ~3~.