Gấp cây

Cho một cây gồm $n$ đỉnh. Ta được phép thực hiện thao tác sau nhiều lần:

Chọn một đỉnh $v$ và hai đường đi có cùng độ dài, cùng xuất phát từ $v$ và chỉ chung nhau đúng đỉnh $v$: $$a_0=v,a_1,\dots ,a_k\text{và}{b}_0=v,b_1,\dots ,b_k.$$ Ngoài ra, các đỉnh $a_1,\dots ,a_k,b_1,\dots ,b_k$ không được có đỉnh kề nào khác ngoài các đỉnh liền kề trên chính đường đi tương ứng của chúng. Khi đó ta có thể gộp một đường đi vào đường đi kia, tức là các đỉnh $b_1,\dots ,b_k$ bị xóa đi (hai đường đi trùng khít lên nhau).

Hãy xác định xem có thể biến cây đã cho thành một đường đi đơn (một chuỗi đỉnh nối tiếp) bằng một dãy các thao tác như trên hay không. Nếu được, hãy tìm số cạnh nhỏ nhất của đường đi thu được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số đỉnh của cây.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ mô tả một cạnh của cây.

Dữ liệu ra

• In ra $-1$ nếu không thể biến cây thành một đường đi.
• Ngược lại, in ra số cạnh nhỏ nhất của đường đi thu được.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le u,v\le n$, $u\ne v$
• Dữ liệu đảm bảo đồ thị đã cho là một cây.

Ví dụ