Cho một cây vô hướng ~n~ đỉnh (các đỉnh đánh số ~1, 2, ..., n~) và một đỉnh ~r~ là đỉnh gốc. Bằng cách định hướng lại các cạnh của cây từ gốc, mỗi đỉnh sẽ là gốc của một cây con. Hãy tìm độ dài đường đi dài nhất và dài nhì (tính bằng số cạnh) của đường đi đơn từ mỗi đỉnh đến các đỉnh con, cháu... của nó.

Input:

• Dòng đầu tiên gồm 2 số nguyên ~n~ và ~r~ (~n <= 10^5~)
• ~N-1~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u~ và ~v~ thể hiện cạnh của cây

Output: Gồm ~n~ dòng, dòng thứ ~i~ gồm 2 số nguyên là đường đi dài nhất và dài nhì của đỉnh ~i~