Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Fuyu và Natsu là hai người bạn vô cùng thân thiết, dù tính cách đối lập nhau hệt như tên gọi.

Natsu mới vẽ bản thảo xây dựng một ngôi nhà chung cho Hội đồng, gồm N gian khác nhau được liên kết bởi N cổng không gian 2 chiều. Thiết kế của Natsu đảm bảo từ một gian, ta hoàn toàn có thể đi đến bất kỳ gian nào khác.

Tuy nhiên, sự cố xảy ra khi cô tiến hành xây dựng: nguyên liệu chỉ đủ để xây N-1 cổng không gian khác nhau! Hay nói cách khác, Natsu phải bỏ một cổng khỏi bản thảo của mình.

Dĩ nhiên, bỏ cổng nào là quyết định chung của cả Hội đồng. Nhưng để tiết kiệm thời gian, Natsu cũng phải tìm ra những cổng có thể loại được – nghĩa là, dù loại đi cổng đó, từ một gian phòng, ta vẫn có thể đi tới bất kỳ gian phòng nào khác. Nhưng tính toán quá phức tạp không phải thế mạnh của Natsu, và cô đã bắt đầu hoảng!

May thay, Fuyu cũng đang ở đó, và chỉ vài giây sau, hai người bạn đã lập đủ danh sách các cổng đủ điều kiện loại bỏ (tất nhiên có sự hỗ trợ của công nghệ). Còn bạn, bạn có thể làm được chứ?

Natsu và Fuyu đang chuẩn bị đi ăn kem, và Natsu hứa sẽ mời cả bạn đi cùng nếu như bạn có thể giải quyết vấn đề này nhanh hơn Fuyu đó! :>

Input

Dòng đầu tiên chứa một số nguyên T (1 ≤ T ≤ 4) là số bộ test.

Tiếp theo đó là T bộ test, tất cả đều tuân theo định dạng sau:

Dòng đầu tiên của mỗi bộ test chứa một số nguyên N duy nhất, là số gian của ngôi nhà chung (3 ≤ N ≤ 10⁵).

N dòng tiếp theo, mỗi dòng gồm 2 số nguyên L, R (1 ≤ L, R ≤ N, L ≠ R); cho biết có cổng nối hai gian L và R. Input đảm bảo rằng, với mỗi bộ test, không có 2 gian nào có nhiều hơn 1 cổng nối, và từ một gian luôn có thể đi tới một gian khác bất kỳ.

Output

Mỗi bộ test gồm 2 dòng với định dạng như sau:

Dòng đầu tiên in ra một số nguyên K (1 ≤ K ≤ N) là số cổng thỏa mãn. Hiển nhiên luôn có ít nhất một cổng thỏa mãn, theo lý thuyết đồ thị.

Dòng thứ hai in ra K số nguyên, là số thứ tự của các cổng thỏa mãn, sắp xếp tăng dần (thứ tự như thứ tự trên input).

Example

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

Output:
3
1 2 4