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

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

Bạn được cho hai cây. Hãy thêm một cạnh giữa chúng sao cho đường kính thu được khi gộp hai cây lại là nhỏ nhất.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ ~(2 \le n \le 2\times10^5)~ - số lượng đỉnh trong cây đầu tiên.

• ~n - 1~ dòng tiếp theo mô tả cây, dòng thứ ~i~ bao gồm hai số nguyên ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le n, u_i ≠ v_i)~ - một cạnh trên cây.

• Dòng tiếp theo gồm một số nguyên ~m~ ~(2 \le m \le 2\times10^5)~ - số lượng đỉnh trong cây thứ hai.

• ~m - 1~ dòng tiếp theo mô tả cây, dòng thứ ~i~ bao gồm hai số nguyên ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le n, u_i ≠ v_i)~ - một cạnh trên cây.

Output

• In ra một số nguyên duy nhất là giá trị của đường kính nhỏ nhất.

Sample Input 1

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

Sample Output 1

5

Bạn thức dậy, không biết bằng cách nào, tại một nơi giống như mê cung vô tận với ánh sáng huỳnh quang mờ nhạt và bầu không khí ngột ngạt. Người ta gọi đây là The Backrooms.

The Backrooms là gì?

Bạn hoàn toàn bị mất phương hướng. Những bức tường mục nát, tiếng ù ù kỳ lạ, và sự im lặng chết chóc khiến bạn nghi ngờ mọi thứ. Bạn không đơn độc, nhưng nhóm của bạn không ở đây. Họ đang quan sát từ xa qua bản đồ. Nhiệm vụ của họ là hướng dẫn bạn tìm ra lối thoát, nhưng nơi đây có nhiều cạm bẫy:

Bản đồ của phòng được biểu diễn dưới dạng một ma trận kích thước ~R~ ~\times~ ~C~, trong đó:

• .: Có thể đứng ở vị trí này.
• '#': Vị trí bức tường.
• 'X': Vị trí có vật cản.
• 'E': Vị trí lối thoát.

Khi nhận được một tọa độ từ người trong phòng, nhóm bên ngoài sẽ phản hồi như sau:

• 'W': Nếu tọa độ là tường.
• 'X': Nếu tọa độ là vật cản.
• 'E': Nếu tọa độ là lối thoát.
• '?': Nếu tọa độ không có đường đến lối thoát

Nếu tọa độ không thuộc các kí tự trên thì họ sẽ mô tả các hướng di chuyển như sau:

• 'L': Di chuyển sang trái.
• 'R': Di chuyển sang phải.
• 'D': Di chuyển xuống dưới.
• 'U': Di chuyển lên trên.

Nếu có nhiều hướng dẫn có thể đưa người chơi đến gần lối thoát hơn, nhóm sẽ ưu tiên lần lượt theo thứ tự: L, D, R, U. Người chơi không thể đi qua tường hoặc vật cản.

NOTE : Lưu ý căn phòng có thể có không hoặc nhiều lối thoát.

Input

• Dòng đầu tiên chứa hai số nguyên ~R~ và ~C~ ~(1 \le R,C \le 1000)~ - kích thước bản đồ của The Backrooms.
• Tiếp theo ~R~ dòng, mỗi dòng chứa ~C~ ký tự - mô tả bản đồ của phòng.
• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~ - là số tọa độ mà người trong phòng sẽ gửi ra.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~i~ và ~j~ - là tọa độ mà người trong phòng gửi ra.

Output

• Với mỗi tọa độ nhận được, in ra một dòng chứa một ký tự, là phản hồi mà nhóm sẽ gửi lại cho người trong phòng.

Sample Input 1

5 5
...##
.E..#
#.X.#
...##
...#.
5
1 1
2 2
3 3
3 1
5 5

Sample Output 1

D
E
X
W
?

Bạn được cung cấp một ma trận ~n~ ~\times~ ~m~ gồm các số nguyên không âm. Giá trị ô ~a_i,_j~ đại diện cho sức mạnh của quái vật tại ô hàng ~i~ và cột ~j~.

Một nhóm quái vật là tập hợp các ô sao cho:

• Mỗi ô trong tập có ~a_i,_j~ > ~0~, và
• Tồn tại một đường đi giữa bất kỳ cặp ô nào trong nhóm bằng cách di chuyên lên, xuống, sang trái hoặc sang phải một số lần và không được đi qua ô có ~a_i,_j~ = ~0~.

Sức mạnh của một nhóm quái vật là tổng sức mạnh của tất cả các ô trong nhóm.

Hãy tìm sức mạnh lớn nhất của một nhóm quái vật trong ma trận.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~,~m~ ~(1 \le n,m \le 1000)~ - số hàng và số cột của ma trận tương ướng.
• Tiếp theo là ~n~ dòng, mỗi dòng chứa ~m~ số nguyên ~a_i,_j~ ~(0 \le a_i,_j \le 1000)~ - sức mạnh của quái vật tại mỗi ô.

Output

• In ra một số nguyên duy nhất là sức mạnh lớn nhất của một nhóm quái vật trong ma trận.

Sample Input 1

3 3
1 2 0
3 4 0
0 0 5

Sample Output 1

10

Sample Input 2

5 5
1 1 1 1 1
1 0 0 0 1
1 0 5 0 1
1 0 0 0 1
1 1 1 1 1

Sample Output 2

16

Vào cuộc họp kín trong buổi tiệc Thank you party vừa qua, chủ nhiệm Rec là lãnh đạo của tổ chức áo đen tại IUH đã tiết lộ một bí mật khủng khiếp cho ~Q~ thành viên thân cận. Tuy nhiên, các thành viên này lại có những người bạn trong IUH mà độ thân thiết còn hơn cả chủ nhiệm Rec, vì thế họ đã đi kể cho bạn của mình nghe (tất nhiên với yêu cầu giữ bí mật, đừng kể cho ai). Tiếc rằng bạn của họ lại đi lan truyền tiếp với tốc độ lan truyền là ~K~, cụ thể như sau:

Vào ngày đầu tiên, mỗi người biết bí mật sẽ kể cho tất cả những người quen trong ~K~ cấp, mỗi người sẽ kể với tất cả người quen của họ (cấp ~1~) rồi những người quen đó lại đi kể tiếp với những người quen khác (cấp ~2~), cứ thế cho đến cấp ~K~. Vào ngày thứ hai, tất cả người biết bí mật sẽ lại kể cho tất cả người quen trong trong ~2K~ cấp và cứ thế đến ngày thứ ~i~ là cấp ~iK~. Cho biết rằng ở IUH có tất cả ~N~ sinh viên được đánh số từ ~1,2,...,N~ và có tất cả ~M~ mối quan hệ bạn bè. Ngoài ra vì tính gắn kết nên bí mật trên đến một lúc nào đó sẽ lan ra toàn bộ các sinh viên, không ai là không biết.

Chủ nhiệm Rec sau khi biết thì rất tức giận nên đã chất vấn các thành viên trong buổi họp kín: với từng sinh viên trong trường, hãy cho biết bạn ấy biết được bí mật vào ngày thứ mấy?

Input

• Dòng đầu tiên ghi bốn số nguyên ~𝑁, 𝑀, 𝑄,𝐾~ với ~1 ≤ 𝑁, 𝑄,𝐾 ≤ 10^5~; ~𝑄 ≤ 𝑁~ và ~1 ≤ 𝑀 ≤ 2.10^5~.
• Dòng tiếp theo ghi ~𝑄~ số nguyên cho biết số thứ tự của các SV có trong buổi họp kín (coi như họ biết bí mật vào ngày thứ ~0~).
• Trong ~M~ dòng tiếp theo, mỗi dòng ghi một cặp số nguyên ~𝑢_𝑖~ và ~𝑣_𝑖~ biểu diễn STT của hai sinh viên quen nhau.

Output

• Ghi ra ~N~ số nguyên ở đó số nguyên thứ ~i~ là số ngày mà SV thứ ~i~ biết được bí mật.

Giới hạn:

• Ràng buộc 1: 30% số điểm có ~𝐾 = 1~; ~1 ≤ 𝑁;𝑄 ≤ 100~; ~1 ≤ 𝑀 ≤ 200~.
• Ràng buộc 2: 20% số điểm có ~1 ≤ 𝑁~; ~𝑄 ≤ 100~; ~1 ≤ 𝑀 ≤ 200~;
• Ràng buộc 3: 50% số điểm còn lại theo giả thiết của bài toán.

Sample Input 1

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

Sample Output 1

1 1 2 2 1 0

Sample Input 2

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

Sample Output 2

1 1 1 0 1 0

Sample Input 3

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

Sample Output 3

1 1 1 2 1 0

Cho một cây ~G=(V,E)~ có ~n~ đỉnh. Chia các cạnh của ~G~ thành ~k~ đường đi sao cho mỗi cạnh thì thuộc đúng một đường đi và hai đường đi tùy ý thì đều có đỉnh chung (các đường này có độ dài tùy ý, không nhất thiết phải đồng đều nhau). Hỏi có thể thực hiện được hay không, và nếu được thì số lượng lớn nhất, nhỏ nhất của số đường đi là bao nhiêu?

Input Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 \le n \le 10^5.~ Trong ~n-1~ dòng tiếp theo, mỗi dòng gồm một cặp số ~(a,b)~ nguyên dương với ~1 \le a, b \le n~ cho biết đỉnh ~a,b~ nối nhau. Dữ liệu đảm bảo là một cây.

Output

Nếu không thể thực hiện được thì in ra ~-1~. Còn nếu tồn tại cách thực hiện thì lần lượt in ra giá trị lớn nhất, nhỏ nhất của ~k~, số đường đi có thể phân chia được.

Sample input

3
1 2
1 3

Sample output

2 1

Giải thích Trong Ví dụ, ta thấy rằng có thể phân hoạch thành ~2~ đường đi gồm ~(1,2),(1,3)~ hoặc ~1~ đường đi là ~(2,1,3).~

Minh đang sắp đón chào một chú hải cẩu mới về trạm nghiên cứu tại cực Bắc của mình, nơi mà cậu sẽ phải đưa nó đi qua các khu trong trạm để tới nơi ở mới của nó. Tại trạm của cậu, cơ sở vật chất đã cũ mà bầy hải cẩu con nào con nấy lại đều to béo, nên cậu khá lo khi việc đưa thêm một bé nặng trĩu đi ngang qua nữa có thể khiến lớp băng dưới khu đó nứt ra!

Cụ thể hơn, trạm của Minh gồm các khu xếp thành một bảng ~M \cdot N~ đánh số từ 1 theo thứ tự từ trên xuống và từ trái qua, khu ở hàng ~i~ cột ~j~ có thể chịu thêm sức nặng tối đa là ~A_{i, j}~. Cậu cần đưa nó đến khu ~(M, N)~ từ cổng vào trạm ở vị trí ~(1, 1)~, ở mỗi khu cậu có thể qua các khu kề cạnh khu hiện tại. Liệu chú hải cẩu này có thể có cân nặng tối đa là bao nhiêu để Minh có thể đưa nó an toàn đến khu của nó?

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~M~, ~N~ cho biết độ lớn của trạm nghiên cứu. (~1 \leq M, N \leq 10^3~).
• ~M~ dòng tiếp theo, mỗi dòng ghi ~N~ số nguyên dương là sức chịu của từng khu (~1 \leq A_{i, j} \leq 10^9~).

Output

Ghi ra một số duy nhất cho biết cân nặng tối đa của chú hải cẩu mà Minh có thể mang theo.

Sample input

3 3
1 2 3
4 5 6
7 8 9

Sample output

1

Subtask

• ~30\%~ số test có ~1 \leq M, N \leq 3~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.

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

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

​