Mã thẻ công dân

Nhằm đổi mới việc quản lí cư dân, chính phủ đưa ra chủ trương cấp thẻ công dân thay cho giấy chứng minh nhân dân và giao quyền cấp mã thẻ cho các tỉnh thành phố trực thuộc trung ương. Để phục vụ cho công việc tạo mã thẻ, đơn vị cấp mã thẻ địa phương đã thu thập thông tin về mối quan hệ quen biết nhau của cư dân trong địa bàn của mình. Mối quan hệ đó được mô tả bởi đơn đồ thị vô hướng liên thông với $n$ đỉnh, mỗi đỉnh tương ứng với một người, hai đỉnh được nối với nhau bởi một cạnh nếu hai người tương ứng là quen biết nhau. (Chú ý là mối quan hệ quen biết ở đây là hai chiều, nghĩa là nếu người $A$ quen biết người $B$ thì người $B$ cũng quen biết người $A$ và ngược lại). Tiếp theo, công việc tạo mã thẻ công dân được tiến hành theo hai bước sau:

Bước 1: Số hóa thông tin về quan hệ quen biết của toàn bộ cư dân bằng cách sắp xếp danh sách cư dân theo thứ tự từ điển không giảm của tên người (hai người trùng tên thì thứ tự giữa hai người là tùy ý), và theo danh sách đã sắp xếp, lần lượt đánh số các đỉnh tương ứng của đồ thị bắt đầu từ $1$.

Bước 2: Mỗi đỉnh $i$ của đồ thị được gán một nhãn $Q_i$ là một bộ có thứ tự gồm chỉ số của một số đỉnh được tạo bởi thuật toán sau đây:

• Khởi tạo nhãn của đỉnh $1$ là $Q_1=(0)$, các đỉnh còn lại là chưa có nhãn; đỉnh $1$ là đã có nhãn nhưng nhãn của nó là chưa cố định.
• Tại mỗi bước trong $n$ bước tiếp theo, thực hiện các thao tác sau:
  • Tìm $u$ là đỉnh có chỉ số nhỏ nhất trong số các đỉnh đã có nhãn chưa cố định;
  • Cố định nhãn đỉnh $u$;
  • Với mỗi đỉnh $v$ kề với đỉnh $u$ (nghĩa là có cạnh nối $u$ với $v$):
    • Nếu $v$ chưa có nhãn thì khởi tạo nhãn của $v$ là $Q_v=(u)$;
    • Nếu $v$ có nhãn chưa cố định thì thêm đỉnh $u$ vào cuối nhãn hiện thời $Q_v$ của $v$.

Quan sát các nhãn thu được, Trưởng ban tin học hóa việc quản lý cư dân thấy rằng các nhãn $Q$ được tạo ra tuy thuận tiện cho quản lý nhưng không tuân theo thứ tự từ điển. Trưởng ban yêu cầu đánh số lại các đỉnh của đồ thị về mối quan hệ quen biết sao cho bộ nhãn của các đỉnh thu được theo thuật toán ở Bước $2$ thỏa mãn tính chất sau: nếu $u<v$ thì nhãn của đỉnh $u$ ($Q_u$) phải đi trước nhãn của đỉnh $v$ ($Q_v$) trong thứ tự từ điển hoặc trùng với nó.

Nhắc lại: Ta nói $Q_u=(p_1,\dots ,p_i)$ là đi trước $Q_v=(q_1,\dots ,q_j)$ trong thứ tự từ điển nếu như:

• hoặc $p_1<q_1$;
• hoặc $(p_1=q_1),\dots ,(p_k=q_k),(p_{k+1}<q_{k+1})$ với $k<min(i,j)$;
• hoặc $(p_1=q_1),\dots ,(p_i=q_i)$ với $i<j$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $m$ được ghi cách nhau bởi dấu cách là số đỉnh và số cạnh của đồ thị về mối quan hệ quen biết.
• Mỗi dòng trong số $m$ dòng tiếp theo chứa $2$ số nguyên được ghi cách nhau bởi dấu cách là hai chỉ số của hai đỉnh đầu mút của một cạnh.

Dữ liệu ra

In ra $n$ số nguyên $d_1,d_2,\dots ,d_n$ cách nhau bởi dấu cách, trong đó $d_i$ là chỉ số của đỉnh $i$ của đồ thị quan hệ quen biết theo cách đánh số thỏa mãn yêu cầu đã nêu. Nếu có nhiều cách đánh số thỏa mãn, in ra một cách bất kỳ.

Ràng buộc

• $2\le n\le 2\times {10}^4$, $1\le m\le 2\times {10}^6$;
• đồ thị là đơn đồ thị vô hướng liên thông.

Subtasks

• Subtask 1 ($30\%$ số test): $n\le 10$;
• Subtask 2 ($30\%$ số test): $n\le 1000$, $m\le {10}^4$;
• Subtask 3 ($40\%$ số test): $n\le 2\times {10}^4$, $m\le 2\times {10}^6$.

Ví dụ