Để cải thiện kiến thức toán học của mình, Bessie đã tham gia khóa học lý thuyết đồ thị và gặp khó khăn với bài toán sau. Hãy giúp cô ấy!

Bạn nhận được đồ thị vô hướng liên thông với các đỉnh được đánh số từ \(1\) đến \(N\) và các cạnh được đánh số từ \(1\) đến \(M\). Với mỗi đỉnh \(v\) trên đồ thị, ta sẽ thực hiện các thao tác sau theo thứ tự:

1. Cho tập \(S = \{v\}\) và giá trị \(h = 0\).
2. Trong khi \(|S|\)(số lượng phần tử của tập \(S\)) \(< N\):
   2.1. Chọn cạnh \(e\) có chỉ số nhỏ nhất sao cho có chính xác một đầu mút của cạnh \(e\) thuộc tập \(S\).
   2.2. Thêm đầu mút còn lại của cạnh \(e\) (điểm không thuộc \(S\)) vào tập \(S\).
   2.3. Cập nhập \(h = 10h + e\)
   (Nếu \(|S| < N\) thì quay về bước 2)
3. Trả về giá trị \(h\) (mod \(10^9 + 7\)).

Hãy xác định tất cả giá trị trả về của mỗi đỉnh sau khi thực hiện các thao tác trên.

Input

• Dòng đầu tiên chứa 2 số nguyên \(N\) và \(M\) mô tả số lượng đỉnh và số lượng cạnh \((2 \le N \le 2 \times 10^5, N−1 \le M \le 4 \times 10^5)\).
• Tiếp theo là \(M\) dòng, dòng thứ \(e^{th}\) chứa hai điểm đầu mút \((a_e, b_e)\) mô tả cạnh thứ \(e^{th}\) của đồ thị \((1 \le a_e < b_e \le N)\). Dữ liệu đảm bảo tất cả các cạnh đã cho tạo thành một đồ thị liên thông, và có tối đa một cạnh nối giữa 2 đỉnh bất kỳ.

Output

• In ra \(N\) dòng, dòng thứ \(i\) chứa giá trị trả về của quá trình bắt đầu từ đỉnh \(i\).
• Lưu ý rằng bạn cần xuất các kết quả theo modulo 10⁹ + 7.

Scoring

• Subtask 1: \(N, M \le 2000\)
• Subtask 2: \(N \le 2000\)
• Subtask 3: \(N \le 10000\)
• Subtask 4: \(a_e + 1 = b_e\) cho tất cả \(e\)
• Subtask 5: Không có ràng buộc bổ sung.

Example

3 2
1 2
2 3

12
12
21

5 6
1 2
3 4
2 4
2 3
2 5
1 5

1325
1325
2315
2315
5132

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081