Ông Malnar đặt mua một cây có ~N~ đỉnh, các đỉnh được gắn nhãn ~1, 2, \ldots, N~. Không may đã xảy ra nhầm lẫn với bên gửi hàng, nên ông nhận được tới ~N~ bản sao của cùng một cây đó.

Trong lúc chờ phản hồi, ông bắt đầu đặt các cây này lên một đa giác đều cũng có ~N~ đỉnh, các đỉnh của đa giác cũng được gắn nhãn ~1, 2, \ldots, N~. Cụ thể, với mỗi bản sao của cây, ông ánh xạ từng đỉnh của cây lên một đỉnh của đa giác sao cho không có hai đỉnh nào của cùng một cây bị đặt lên cùng một đỉnh của đa giác.

Ông Malnar nhanh chóng nhận ra rằng toàn bộ các đường chéo và các cạnh của đa giác đều đã được phủ bởi các cạnh của các bản sao cây. Để chắc rằng đó không phải ngẫu nhiên, ông thử dựng lại từ đầu nhưng thấy quá khó, nên ông nhờ bạn giúp.

Nói chính xác hơn, ông cần tìm các số nguyên ~p_{ij}~ với ~1 \le i, j \le N~ sao cho:

• với mọi ~i~, dãy ~p_{i1}, p_{i2}, \ldots, p_{iN}~ là một hoán vị của ~1, 2, \ldots, N~;
• với mọi cặp ~1 \le i < j \le N~, tồn tại một hàng ~k~ sao cho cạnh nối hai đỉnh ~p_{ki}~ và ~p_{kj}~ là một cạnh của cây đã cho.

Có thể chứng minh rằng luôn tồn tại một cách xây dựng như vậy với mọi cây.

Input

Dòng đầu tiên chứa một số nguyên ~N~, là số đỉnh của cây và cũng là số đỉnh của đa giác.

Mỗi trong ~N-1~ dòng tiếp theo chứa hai số nguyên ~u~ và ~v~, là hai đầu mút của một cạnh trong cây.

Output

In ra các số ~p_{ij}~ trên ~N~ dòng.

Dòng thứ ~i~ phải in ra ~p_{i1}, p_{i2}, \ldots, p_{iN}~ theo đúng thứ tự đó.

Ràng buộc

• ~3 \le N \le 2000~
• ~1 \le u, v \le N~

Chấm điểm

• Subtask 1 (10 điểm): Tồn tại một đỉnh ~u~ nằm trong mọi cạnh
• Subtask 2 (15 điểm): ~N \le 10~
• Subtask 3 (20 điểm): Cây là một đường thẳng
• Subtask 4 (25 điểm): ~N \le 300~
• Subtask 5 (40 điểm): Không có ràng buộc bổ sung.

Sample Input 1

3
1 2
1 3

Sample Output 1

2 3 1
1 2 3
3 1 2

Sample Input 2

4
1 2
1 3
2 4

Sample Output 2

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

Sample Input 3

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

Sample Output 3

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