Cho một cây có \(N\) đỉnh được gán nhãn từ \(1\) đến \(N\). Cũng có một đa giác đều \(N\) đỉnh với các vị trí được đánh số từ \(1\) đến \(N\). Hãy đặt \(N\) bản sao của cây lên đa giác: trong mỗi bản sao, các đỉnh cây được đặt vào các vị trí khác nhau. Tương đương, cần in các số \(p_{ij}\) sao cho mỗi hàng \((p_{i1},p_{i2},\ldots,p_{iN})\) là một hoán vị của \(1..N\), và với mọi cặp vị trí \(a<b\), tồn tại một hàng \(i\) mà \(p_{ia}\) và \(p_{ib}\) là hai đầu mút của một cạnh cây. Nói cách khác, hợp các cạnh của mọi bản sao phải phủ mọi cạnh và đường chéo của đa giác. Đề bài bảo đảm luôn tồn tại lời giải.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\) (\(3\le N\le2000\)), là số đỉnh của cây và của đa giác. \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) (\(1\le u,v\le N\)), biểu diễn một cạnh của cây.

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) chứa \(p_{i1},p_{i2},\ldots,p_{iN}\) theo thứ tự. Mỗi hàng phải là một hoán vị hợp lệ; chấp nhận bất kỳ cấu trúc nào thỏa các điều kiện trên.

Ràng buộc

Các giới hạn chính thức được nêu trong phần Dữ liệu vào.

Phân nhóm

1. \(10\) điểm: tồn tại một đỉnh thuộc mọi cạnh của cây.
2. \(15\) điểm: \(N\le10\).
3. \(20\) điểm: cây là một đường đi.
4. \(25\) điểm: \(N\le300\).
5. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

3
1 2
1 3

2 3 1
1 2 3
3 1 2

4
1 2
1 3
2 4

1 4 3 2
3 2 1 4
2 1 4 3
4 3 2 1

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

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

Nguồn

COCI 2025/2026 - Vòng 5, bài Slaganje.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.