Giải bài trực tuyến

Trang trại của bác Ba có N (1 <= N <= 10,000) cánh đồng nối với nhau bởi N-1 đường nối hai chiều sao cho mỗi cặp cánh đồng đều được nối bởi một dãy các con đường nào đó.

Trang trại rộng đến nỗi mà theo năm tháng, các chủ trang trại (gồm cả bác Ba) đã vẽ rất nhiều tấm bản đồ khác nhau, tên của các cánh đồng cũng thay đổi theo thời gian.

Bác Ba khám phá ra một hộp đựng T (2 <= T <= 10) tấm bản đồ cũ kỹ trong hộc tủ nhà mình. Bác tò mò muốn biết những tập bản đồ nào mô tả cùng một mô hình trang trại. Hai tấm bản đồ mô tả cùng một mô hình trang trại nếu ta có thể thay đổi nhãn các đỉnh trong một tấm bản đồ để thu được tấm bản đồ còn lại.

Input

Dòng 1 chứa hai số T và N.

T nhóm dòng tiếp theo, mỗi nhóm dòng gồm N-1 dòng, mỗi dòng chứa hai số nguyên x, y (1 <= x, y <= N) mô tả một đường nối của tấm bản đồ tương ứng.

Output

In ra T dòng, dòng thứ i gồm chỉ số của các tấm bản đồ mô tả cùng một mô hình trang trại với tấm bản đồ thứ i (gồm chính i) theo thứ tự tăng dần.

Example

Input:
3 4
1 4
4 3
2 4
2 3
1 3
3 4
4 2
2 1
1 3

Output:
1 2
1 2
3