huyhau6a2 là 1 người rất thích chơi với cây. Vài hôm trước cậu đã mua về 1 cây thần kỳ, cây này bao gồm $n$ đỉnh. Ngoài ra, cây của huyhau6a2 còn có khả năng đặc biệt là có thể thay đổi gốc bất cứ lúc nào.

Chơi với cây quá chán, cậu quyết định rủ người anh em (khác cha khác mẹ) Kubogi vào chơi cây cùng mình và anh Kubogi đã nghĩ ra 1 trò chơi, trò chơi như sau:

Với mỗi lần, Kubogi sẽ đổi gốc của cây thành $x$, và huyhau6a2 phải tìm $LCA(u,v)$. Trong đó $LCA(u,v)$ là tổ tiên chung gần nhất của 2 đỉnh $u$ và $v$.

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

2
5
2
1
1