An đang vận hành hệ thống giao dịch cổ phiếu liên thông. Mối quan hệ tương đồng giữa \(N\) mã cổ phiếu lớn được mô tả bằng một đồ thị liên kết vô hướng. Mỗi nút trên đồ thị đại diện cho một mã cổ phiếu (chứa ID và danh sách các mã liên kết trực tiếp).

Để phục vụ bảo trì hệ thống mà không ảnh hưởng đến dữ liệu thực, An cần lập trình một thuật toán để nhân bản chính xác (Deep Copy/Clone Graph) đồ thị mạng lưới cổ phiếu này. Bản sao phải hoàn toàn độc lập về vùng nhớ với đồ thị gốc.

Hãy giúp An viết mã nguồn thực hiện nhân bản đồ thị. Đối với bài tập này, bạn cần thiết kế thuật toán duyệt đồ thị sao chép toàn bộ liên kết và in ra checksum kiểm tra cấu trúc liên kết sau khi clone để xác thực.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả liên kết hai chiều giữa cổ phiếu \(u\) và cổ phiếu \(v\).

Định dạng đầu ra

• In ra \(N\) dòng, dòng thứ \(u\) (\(1 \le u \le N\)) chứa danh sách các cổ phiếu liên kết với \(u\) trên đồ thị mới đã được sắp xếp tăng dần.

Ví dụ

Input:

4 4
1 2
2 3
3 4
4 1

Output:

2 4
1 3
2 4
1 3