Gốc, cha và độ sâu

Cho một cây gồm $n$ đỉnh đánh số từ $1$ đến $n$ và $n-1$ cạnh vô hướng. Ta chọn đỉnh $r$ làm gốc của cây.

Với mỗi đỉnh $v$, hãy cho biết:

• cha của $v$: đỉnh kề với $v$ nằm trên đường đi từ $v$ về gốc $r$ (gốc không có cha, quy ước cha của gốc là $0$);
• độ sâu của $v$: số cạnh trên đường đi từ $r$ tới $v$ (độ sâu của gốc là $0$).

Lưu ý: mỗi cạnh được cho dưới dạng hai đầu mút theo thứ tự bất kỳ, không nhất thiết đỉnh đứng trước là cha.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $r$.
• $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 nối $u$ và $v$.

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

Dữ liệu ra

• Dòng thứ nhất: $n$ số nguyên, số thứ $v$ là cha của đỉnh $v$.
• Dòng thứ hai: $n$ số nguyên, số thứ $v$ là độ sâu của đỉnh $v$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le r\le n$
• $1\le u,v\le n$, $u\ne v$

Ví dụ