Một ngôi làng có \(N\) ngôi nhà, mỗi nhà có đúng một người dân sinh sống. Các ngôi nhà được nối với nhau bằng những con đường. Mỗi con đường nối hai ngôi nhà và dài đúng \(1\) kilômét. Từ bất kỳ ngôi nhà nào cũng có thể đến bất kỳ ngôi nhà nào khác qua một hoặc nhiều con đường liên tiếp. Trong làng có tổng cộng \(N-1\) con đường.

Một ngày nọ, tất cả người dân quyết định chuyển sang nhà khác. Sau khi chuyển, mỗi ngôi nhà vẫn phải có đúng một người ở, nhưng không ai được ở lại ngôi nhà cũ của mình. Ta muốn biết giá trị nhỏ nhất và lớn nhất có thể của tổng độ dài các đường đi ngắn nhất từ nhà cũ đến nhà mới của tất cả người dân, tính bằng kilômét.

Hãy viết chương trình tìm cả hai giá trị này và đưa ra một cách phân nhà mới tương ứng cho mỗi trường hợp. Ngôi làng có bảy ngôi nhà minh họa ở Hình 1 và hai cách chuyển nhà được trình bày trong phần giải thích Ví dụ 2.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Các ngôi nhà được đánh số bằng các số nguyên liên tiếp \(1,2,\ldots,N\).

\(N-1\) dòng tiếp theo mô tả các con đường. Mỗi dòng chứa hai số nguyên \(a,b\), cho biết có một con đường nối hai ngôi nhà \(a\) và \(b\).

Dữ liệu ra

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách: giá trị nhỏ nhất và lớn nhất của tổng độ dài các đường đi ngắn nhất, tính bằng kilômét.

Dòng thứ hai mô tả một cách phân nhà mới hợp lệ đạt tổng độ dài nhỏ nhất: \(N\) số nguyên đôi một khác nhau \(v_1,v_2,\ldots,v_N\), cách nhau bởi dấu cách. Với mỗi \(i\), \(v_i\) là số hiệu ngôi nhà mà người dân ban đầu ở nhà \(i\) sẽ chuyển đến, và \(v_i\ne i\). Nếu có nhiều cách hợp lệ, có thể in bất kỳ cách nào.

Dòng thứ ba mô tả một cách phân nhà mới hợp lệ đạt tổng độ dài lớn nhất, theo cùng định dạng.

Ràng buộc

• \(1<N\le10^5\).
• \(1\le a,b\le N\), \(a\ne b\).
• Có đúng \(N-1\) con đường, mỗi con đường dài \(1\) kilômét; từ mỗi ngôi nhà đều có thể đi đến mọi ngôi nhà khác.
• Giới hạn thời gian: \(0{,}7\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(12\) điểm: \(N\le10\).
2. \(38\) điểm: \(N\le1000\).
3. \(50\) điểm: không có ràng buộc thêm.

Bạn được \(50\%\) số điểm nếu, với mỗi bộ dữ liệu, kết quả chứa đúng tổng độ dài và một cách phân nhà hợp lệ cho một trong hai trường hợp: tổng độ dài nhỏ nhất hoặc tổng độ dài lớn nhất. Tuy nhiên, vẫn phải in phần mô tả cho cả hai trường hợp, mỗi phần gồm \(N\) số nguyên trong đoạn từ \(1\) đến \(N\), cách nhau bởi dấu cách. Đối với trường hợp có thể không đúng, các số này có thể là bất kỳ giá trị nào trong đoạn đó, chẳng hạn đều bằng \(1\).

Ví dụ

4
1 2
2 3
3 4

4 8
2 1 4 3
4 3 2 1

7
4 2
5 7
3 4
6 3
1 3
4 5

8 18
6 4 1 2 7 3 5
7 3 4 1 2 5 6