Dây chuyền sản xuất nhà máy VAIP có ~n~ vị trí sản xuất được đánh số ~\{1,2,\ldots,n\}~ và bố trí dưới dạng một đồ thị có cấu trúc như sau:

• mỗi một vị trí sản xuất là một đỉnh của đồ thị;
• hai vị trí kề nhau tương ứng với cạnh của đồ thị;
• đồ thị là vô hướng liên thông và không có chu trình.

Có ~n~ công nhân được đánh số ~\{1,2,\ldots,n\}~ được được đào tạo để phụ trách các vị trí trong dây chuyền. Do sở trường của mỗi người nên người ~i~ sẽ cảm thấy hạnh phúc nếu được xếp phụ trách ở vị trí ~i~ (~\forall i, 1\leq i\leq n~). Ban đầu các công nhân được bố trí đúng vị trí hạnh phúc của mình, nghĩa là người ~i~ được bố trí ở vị trí ~i~. Để có thể thích ứng với nhiều vị trí khác nhau mà không làm ảnh hưởng sản xuất, sau mỗi ngày, người quản lý chọn ra đúng hai công nhân kề nhau, nghĩa là ở vị trí hai đỉnh kề nhau trên đồ thị, và đảo vị trí của họ. Sau một số ngày đảo chỗ, đến hôm nay người quản lý nhận ra là quên mất không ghi lại nhật ký vị trí các lần đảo để có thể làm ngược lại quá trình những ngày vừa qua nhằm đưa tất cả công nhân về vị trí hạnh phúc của họ.

Yêu cầu: Cho biết vị trí các công nhân hiện đang phụ trách ngày hôm nay, bạn hãy giúp người quản lý tìm ra thứ tự đảo vị trí hai công nhân mỗi ngày để đưa tất cả công nhân về vị trí hạnh phúc của họ sao cho số ngày phải sử dụng là ít nhất có thể.

Đây là bài toán chỉ cần nộp các file kết quả đầu ra. Thí sinh được cho 10 file đầu vào tương ứng với 10 test, đối với mỗi file đầu vào thí sinh cần nộp một file kết quả đầu ra mô tả kế hoạch hoán đổi vị trí theo từng ngày. Với mỗi file kết quả đầu ra mô tả đúng đắn quá trình hoán đổi, điểm của thí sinh phụ thuộc vào số ngày sử dụng để đưa toàn bộ công nhân về vị trí hạnh phúc (xem cách tính điểm trong phần Chấm điểm).

Dữ liệu

Thí sinh được cung cấp 10 file dữ liệu đầu vào với tên tương ứng là: input_0.txt, input_1.txt, ~\ldots~, input_9.txt. Mỗi file dữ liệu đầu vào có khuôn dạng như sau:

• Dòng đầu chứa một số nguyên dương ~n~ là số đỉnh của đồ thị;
• Mỗi dòng trong số ~n-1~ dòng tiếp theo chứa hai số nguyên dương ~u~ và ~v~ là hai đỉnh đầu mút một cạnh của đồ thị;
• Dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~i~ là số hiệu của công nhân hiện đang đứng tại vị trí ~i~.

Các số trên một dòng cách nhau bởi dấu cách.

File input thí sinh có thể tải xuống ở đây.

Kết quả

Đối với mỗi file dữ liệu đầu vào, thí sinh cần nộp một file kết quả đầu ra mô tả kế hoạch hoán đổi vị trí theo từng ngày, các file kết quả đầu ra có tên tương ứng là: output_0.txt, output_1.txt,~\ldots~, output_9.txt. Mỗi file kết quả đầu ra có khuôn dạng:

• Dòng đầu tiên chứa một số nguyên ~t~ là số ngày bạn cần để đưa tất cả công nhân về vị trí hạnh phúc;
• Dòng thứ ~i~ trong số ~t~ dòng tiếp theo ghi hai số nguyên dương ~u~ và ~v~ là hai vị trí sản xuất mà công nhân ở đó phải đảo chỗ ngày thứ ~i~.

Thí sinh cần nén các file kết quả đầu ra thành một file có tên submission.zip để nộp. Điểm số của bài là tổng điểm của từng test.

Lưu ý: Kích thước tối đa cho phép của file zip nộp lên server là 10MB.

Giới hạn

• Subtask 1 (30 điểm): ~n\leq 10~;
• Subtask 2 (70 điểm): ~10< n \leq 1000~;

Chấm điểm

Với mỗi file dữ liệu đầu vào, gọi GK là số ngày cần để đưa toàn bộ công nhân về vị trí hạnh phúc của họ theo phương án của Ban giám khảo (giá trị này thí sinh không được biết, chỉ dùng khi chấm), TS là số ngày cần để đưa toàn bộ công nhân về vị trí hạnh phúc của họ theo phương án của thí sinh trong file đầu ra tương ứng với file đầu vào. Đặt ~P=(TS-GK)/GK~ , khi đó, thí sinh sẽ nhận được:

• 0 điểm nếu ~P>1~;
• 10 điểm nếu ~P\leq 0~;
• ~-\log_{10}(P \times 0.9999+0.0001) \times 2.5~ điểm nếu ~0< P \leq 1~;

trên tổng số ~10~ điểm của test đó.

Lưu ý: Thí sinh sẽ không được điểm nếu file output nộp lên không hợp lệ.

Sample Input

3
1 2
2 3
2 1 3

Sample Output

1
1 2