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

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 đồ thị có chu trình hay không?.

Chu trình là đường đi xuất phát từ một đỉnh, đi qua các cạnh và quay trở lại đỉnh ban đầu

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: nếu có chu trình thì in ra "YES". Ngược lại in ra "NO".

Examples

Input

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

Output

YES

*Giải thích: * Một chu trình đó là 3->5->1->3

Hoặc chu trình 1->2->4->5->1

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

​

Có n thành phố và ban đầu không có con đường nào nối giữa chúng. Tuy nhiên, mỗi ngày sẽ có một con đường hai chiều mới được xây dựng và sẽ có tổng cộng m con đường.

Thành phần liên thông là một nhóm các thành phố mà giữa hai thành phố bất kỳ trong thành phần liên thông đều có đường đi.

Sau mỗi ngày, nhiệm vụ của bạn là tìm số thành phần liên thông và kích thước của thành phần liên thông lớn nhất lớn nhất.

Input

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

Tiếp theo là m dòng mô tả những con đường mới. Mỗi dòng có hai số nguyên u và v: một con đường hai chiều mới được xây dựng giữa thành phố u và v.

Output

In m dòng: số thành phần liên thông và kích thước của thành phần liên thông lớn nhất lớn nhất của m ngày

Hạn chế

~1 \le n \le 10^5~

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

~1 \le u, v \le n~

Examples

Input

5 3
1 2
1 3
4 5

Output

4 2
3 3
2 3

Có n thành phố và m con đường. Thật không may, tình trạng đường xá xuống cấp đến mức không thể sử dụng được. Nhiệm vụ của bạn là sửa chữa một số con đường để có một tuyến đường tốt giữa hai thành phố bất kỳ.

Đối với mỗi con đường, bạn biết chi phí sửa chữa của nó và bạn nên tìm giải pháp sao cho tổng chi phí càng nhỏ càng tốt.

Input

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

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

Output

In một số nguyên: tổng chi phí sửa chữa tối thiểu. Tuy nhiên, nếu không có giải pháp thì in ra "IMPOSSIBLE". Hạn chế

~1 \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~

Examples

Input

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

Output

14 

Các con đường được sửa chữa được tô màu đỏ. Tổng chi phí là 3 + 5 + 2 + 4 = 14

Bạn được cho một cây có gốc gồm n nút. Các nút được đánh số 1,2,~\ldots~,n và nút 1 là nút gốc. Mỗi nút có một màu.

Nhiệm vụ của bạn là xác định cho mỗi nút số lượng màu riêng biệt trong cây con của nút đó.

Input

Dòng đầu tiên chứa số nguyên n: số nút. Các nút được đánh số 1,2,~\ldots~,n.

Dòng tiếp theo gồm n số nguyên ~c_1,c_2,...,c_n~: màu của mỗi nút.

Khi đó có n-1 dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên u và v: có một cạnh giữa các nút u và v.

Output

In ra n số nguyên: với mỗi nút 1,2,~\ldots~,n là số lượng màu phân biệt.

Hạn chế

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

~1 \le u, v \le n~

~1 \le c_i \le 10^9~

Examples

Input

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

Output

3 1 2 1 1

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).

Xét một đồ thị có hướng có n nút và m cạnh. Nhiệm vụ của bạn là đếm số đường đi từ nút 1 đến nút n có đúng k cạnh.

Input

Dòng đầu tiên chứa ba số nguyên n, m và k: số nút, cạnh và độ dài của đường đi. Các nút được đánh số 1,2,~\dots~,n.

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

Output

In số đường đi modulo ~10^9+7~.

Hạn chế

~1 \le n \le 100~

~1 \le m \le n(n-1)~

~1 \le k \le 10^9~

~1 \le u, v \le n~

Examples

Input

3 4 8
1 2
2 3
3 1
3 2

Output

2

Giải thích: Các đường đi là

~1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3~

~1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3.~

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

​