Cho một cây gồm n đỉnh đánh số từ 1, 2, ...n và n-1 cạnh hai chiều nối các đỉnh.

Nhiệm vụ của bạn là cho biết thứ tự duyệt theo tìm kiếm chiều sâu từ đỉnh 1.

*Lưu ý: * Thứ tự được sắp sếp theo thứ tự nhập vào của các cạnh. Tức là u sẽ thăm trước v khi u được nhập trước v.

Input

Dòng đầu tiên gồm số n (~ 2 \le n \le 2.10^5 ~) - số đỉnh của cây.

N-1 dòng tiếp theo gồm 2 số u và v (~ 1 \le u, v \le n ~) - có cạnh hai chiều nối từ đỉnh u đến đỉnh v.

Output

Thứ tự duyệt theo tìm kiếm chiều sâu từ đỉnh 1 (theo thứ tự nhập vào)

Examples

Input 1

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

Output 1

6 5 2 7 3 4 1 

Cho một cây gồm n đỉnh đánh số từ 1, 2, ...n và n-1 cạnh hai chiều nối các đỉnh.

Nhiệm vụ của bạn là cho biết thứ tự duyệt theo tìm kiếm chiều rộng từ đỉnh 1.

*Lưu ý: * Thứ tự được sắp sếp theo thứ tự nhập vào của các cạnh. Tức là u sẽ thăm trước v khi u được nhập trước v.

Input

Dòng đầu tiên gồm số n (~ 2 \le n \le 2.10^5 ~) - số đỉnh của cây.

N-1 dòng tiếp theo gồm 2 số u và v (~ 1 \le u, v \le n ~) - có cạnh hai chiều nối từ đỉnh u đến đỉnh v.

Output

Thứ tự duyệt theo tìm kiếm chiều rộng từ đỉnh 1 (theo thứ tự nhập vào)

Examples

Input 1

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

Output 1

1 6 4 2 3 5 7 

Cho đồ thị gồm n đỉnh đánh số từ 1, 2, ...n và m cạnh hai chiều nối các đỉnh.

Nhiệm vụ của bạn là cho biết số thành phần liên thông của đồ thị.

Một thành phần liên thông là một tập các đỉnh mà mỗi cặp đỉnh đều có đường đi giữa chúng.

Input

Dòng đầu tiên gồm 2 số n và m (~ 2 \le n \le 2.10^5 , 1 \le m \le 2.10^5 ~) - số đỉnh và số cạnh của đồ thị.

M dòng tiếp theo gồm 2 số u và v (~ 1 \le u, v \le n ~) - có cạnh hai chiều nối từ đỉnh u đến đỉnh v.

Output

Một dòng duy nhất là số thành phần liên thông của đồ thị.

Examples

Input

6 3 
1 2
4 1
3 5 

Output

3

Giải thích:

• Thành phần liên thông thứ nhất gồm các đỉnh 1, 2, 4

• Thành phần liên thông thứ nhất gồm các đỉnh 3, 5

• Thành phần liên thông thứ nhất gồm các đỉnh 6

Cho đồ thị gồm n đỉnh đánh số từ 1, 2, ...n và m cạnh hai chiều nối các đỉnh.

Nhiệm vụ của bạn là cho biết khoảng cách ngắn nhất từ đỉnh 1 đến đỉnh n.

Khoảng cách giữa hai đỉnh là số đỉnh nằm trên đường đi của hai đỉnh đó.

Nếu từ đỉnh 1 không thể đến được đỉnh n thì in ra "IMPOSSIBLE"

Input

Dòng đầu tiên gồm 2 số n và m (~ 2 \le n \le 2.10^5 , 1 \le m \le 2.10^5 ~) - số đỉnh và số cạnh của đồ thị.

M dòng tiếp theo gồm 2 số u và v (~ 1 \le u, v \le n ~) - có cạnh hai chiều nối từ đỉnh u đến đỉnh v.

Output

Một dòng duy nhất là khoảng cách đường đi ngắn nhất từ 1 đến n.

Examples

Input

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

Output

3

*Giải thích: * Đường đi đó là 1->4->5 (lưu ý là đường đi từ 1 đến n)

Bạn được cung cấp một bản đồ của một tòa nhà, và nhiệm vụ của bạn là đếm số phòng của nó.

Kích thước của bản đồ là n ~\times~ m ô vuông, và mỗi ô vuông có thể là sàn hoặc tường. Bạn có thể di chuyển sang trái, phải, lên và xuống trên sàn (không được phép đi xuyên tường).

Input

Dòng đầu tiên chứa hai số nguyên n và m: chiều cao và chiều rộng của bản đồ.

Tiếp theo là n (~ 1 \le n \le 1000 ~ ) dòng, mỗi dòng chứa m (~ 1 \le m \le 1000 ~ ) ký tự mô tả bản đồ. Mỗi ký tự có thể là . (sàn) hoặc # (tường).

Output

In ra màn hình một số nguyên: số lượng phòng.

Examples

Input

5 8
########
#..#...#
####.#.#
#..#...#
########

Output

3

Có n học sinh trong lớp và có m mối quan hệ bạn bè. Nhiệm vụ của bạn là chia học sinh thành hai nhóm sao cho không có hai học sinh nào trong cùng một nhóm là bạn.

Input

Dòng đầu tiên gồm 2 số n và m (~ 2 \le n \le 2.10^5 , 1 \le m \le 2.10^5 ~) - số học sinh và số mối quen hệ bạn bè. Các học sinh được đánh số từ 1 đến n.

M dòng tiếp theo mô tả các mối quan hệ bạn bè. Mỗi dòng chứa hai số nguyên u và v: học sinh u và v là bạn bè.

Output

In một ví dụ về cách xây dựng hai nhóm. Đối với mỗi học sinh, in "1" hoặc "2" tùy thuộc vào nhóm mà học sinh đó sẽ được gán. Có nhiều cách chia nhóm nhưng bạn hãy tìm cách gán học sinh 1 vào nhóm 1.

Nếu không có cách chia nhóm, in "IMPOSSIBLE".

Examples

Input

5 3
1 2
1 3
4 5

Output

1 2 2 1 2

Có n thành phố và m con đường kết nối giữa chúng. Nhiệm vụ của bạn là xác định độ dài của con đường ngắn nhất từ thành phố 1 đến mọi thành phố.

Input

Dòng đầu tiên chứa hai số nguyên n và m: số thành phố và số con đường kết nối. Các thành phố được đánh số 1,2,...,n.

Sau đó có m dòng mô tả các con đường. Mỗi dòng có ba số nguyên u, v và w: một con đường một chiều bắt đầu ở thành phố u, kết thúc ở thành phố v và có độ dài là w.

Output

In ra n số nguyên: độ dài tuyến đường ngắn nhất từ thành phố 1 đến các thành phố 1,2,...,n.

Hạn chế

~1 \le n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

~1 \le u, v \le n~

~1 \le w \le 10^9~

Examples

Input

6 9
1 2 6 
1 3 1
3 2 3 
3 5 2
2 4 8
4 5 1
5 4 3
4 6 1
5 6 10 

Output

0 4 1 6 3 7

Có n thành phố và m con đường. Nhiệm vụ của bạn là xử lý q truy vấn: xác định độ dài của tuyến đường ngắn nhất giữa hai thành phố x và y.

Input

Dòng đầu tiên chứa 3 số nguyên n, m và q: số thành phố, số đường và truy vấn.

Khi đó có m dòng mô tả các con đường. Mỗi dòng có ba số nguyên u, v và w: có một con đường nối giữa thành phố u và v có chiều dài là w. Mọi con đường đều là đường hai chiều.

Cuối cùng là q dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên x và y: xác định độ dài của tuyến đường ngắn nhất giữa thành phố x và y.

Output In độ dài của tuyến đường ngắn nhất cho mỗi truy vấn. Nếu không có lộ trình, thay vào đó hãy in -1.

Hạn chế

~1 \le n \le 500~

~1 \le m \le n^2~

~1 \le q \le 10^5~

~1 \le a,b \le n~

~1 \le c \le 10^9~

Examples

Input

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Output

5
5
8
-1
3

​

Nhiệm vụ của bạn là tìm k đường bay ngắn nhất từ thành phố 1 đến thành phố n. Một tuyến đường có thể ghé thăm cùng một thành phố nhiều lần.

Input

Dòng đầu tiên chứa 3 số nguyên n, m, k: số thành phố, số con đường và k. Các thành phố được đánh số 1,2,...,n.

Sau đó, đầu vào có m dòng mô tả các con đường. Mỗi dòng có ba số nguyên u, v và w: con đường bắt đầu ở thành phố u, kết thúc ở thành phố v và giá của nó là w. Tất cả các con đường đều là một chiều.

Output

In ra k số nguyên: giá của k tuyến đường rẻ nhất được sắp xếp theo giá của chúng.

Hạn chế

~2 \le n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

~1 \le a,b \le n~

~1 \le c \le 10^9~

~1 \le k \le 10~

Examples

Input

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

Output

4 4 7

Giải thích: Các tuyến rẻ nhất là:

1 -> 3 -> 4 (chi phí 4)

1 -> 2 -> 3 -> 4 (chi phí 4)

1 -> 2 -> 4 (chi phí 7).

Một đồ thị có hướng bao gồm n nút và m cạnh. Các nút được đánh số 1,2,...,n.

Tính toán cho mỗi nút số lượng nút bạn có thể đến được từ nút đó (bao gồm cả chính nút đó).

Input

Dòng đầu tiên chứa hai số nguyên n và m: số nút và số cạnh.

Khi đó có m dòng mô tả các cạnh. Mỗi dòng có hai số nguyên u và v riêng biệt: có một cạnh một chiều từ nút u đến nút v.

Output

In ra n số nguyên: với mỗi nút là số lượng nút có thể truy cập được.

Hạn chế

~1 \le n \le 5 \cdot 10^4~

~1 \le m \le 10^5~

Examples

Input

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

Output

5 3 2 2 1

​