Byteland có ~n~ thành phố, và ~m~ con đường đường giữa chúng. Mục tiêu là xây dựng các con đường mới để có một tuyến đường giữa hai thành phố bất kỳ.

Nhiệm vụ của bạn là tìm ra số lượng đường tối thiểu cần thiết, đồng thời xác định những con đường nào nên được xây dựng.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng thành phố và con đường đường. Các thành phố được đánh số ~1,2,\ldots,n~.
• Sau đó, có ~m~ dòng mô tả các con đường. Mỗi dòng có hai số nguyên ~a~ và ~b~: có một đường giữa các thành phố đó.
• Một con đường luôn kết nối hai thành phố khác nhau, và có nhiều nhất một con đường giữa hai thành phố bất kỳ.

Output

• Đầu tiên in một số nguyên ~k~: số lượng con đường cần thiết.
• Sau đó, in ~k~ dòng mô tả các con đường mới. Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

• ~1 \le n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a, b \leq n~

Example

Sample input

4 2
1 2
3 4

Sample output

1
2 3

Mạng của Syrjälä có ~n~ máy tính và ~m~ kết nối. Nhiệm vụ của bạn là tìm hiểu xem Uolevi có thể gửi tin nhắn cho Maija hay không, và nếu có thể, số lượng máy tính tối thiểu trên một đường tuyền như vậy là bao nhiêu.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng máy tính và kết nối. Các máy tính được đánh số ~1,2,\ldots,n~. Máy tính của Uolevi là ~1~ và máy tính của Maija là ~n~.
• Sau đó, có ~m~ dòng mô tả các kết nối. Mỗi dòng có hai số nguyên ~a~ và ~b~: có một kết nối giữa các máy tính đó.
• Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy tính bất kỳ.

Output

• Nếu có thể gửi tin nhắn, trước tiên hãy in ~k~: số lượng máy tính tối thiểu trên một đường truyền hợp lệ. Sau này, in một ví dụ về một đường truyền như vậy. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
• Nếu không có đường truyền, in IMPOSSIBLE.

Constraints

• ~2 \leq n \leq 10 ^ 5~
• ~1 \leq m \leq 2 \cdot 10 ^ 5~
• ~1 \leq a, b \leq n~

Example

Sample input

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

Sample output

3
1 4 5

Cho trước bản đồ của một tòa nhà, và nhiệm vụ của bạn là đếm số lượng phòng của nó. Kích thước của bản đồ là ~n \times m~ hình vuông, và mỗi hình vuông là sàn hoặc tường. Bạn có thể đi bộ sang trái, phải, lên trên và xuống dưới qua các ô sàn nhà .

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: kích thước của bản đồ.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ ký tự mô tả bản đồ. Mỗi ký tự là . (sàn) hoặc # (tường).

Output

• In một số nguyên: số lượng phòng.

Constraints

• ~1 \leq n, m \leq 1000~

Example

Sample input

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

Sample output

3

Bạn đang chơi một trò chơi bao gồm ~n~ hành tinh. Mỗi hành tinh có một cổng dịch chuyển đến một hành tinh khác (hoặc chính hành tinh đó).

Bạn bắt đầu trên một hành tinh và sau đó đi qua các cổng dịch chuyển cho đến khi bạn đến một hành tinh mà bạn đã thăm trước đó.

Nhiệm vụ của bạn là tính toán cho mỗi hành tinh số lần dịch chuyển sẽ có nếu bạn bắt đầu trên hành tinh đó.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~q~: số lượng hành tinh và truy vấn. Các hành tinh được đánh số ~1,2,\ldots,n~.
• Dòng thứ hai có ~n~ số nguyên ~t_1,t_2,\ldots,t_n~: với mỗi hành tinh, điểm đến của của cổng dịch chuyển. Có thể là ~t_i=i~.

Output

• In ~n~ số nguyên theo đề bài.

Constraints

• ~1 \leq n \leq 2 \cdot 10 ^ 5~
• ~1 \leq t_i \leq n~

Example

Sample input

5
2 4 3 1 4

Sample output

3 3 1 3 4

Nitori Kawashiro cần thiết kế hệ thống cáp treo 2 chiều giữa ~n~ địa điểm. Biết rằng nếu có đường đi giữa địa điểm ~a~ tới địa điểm ~b~ và từ địa điểm ~b~ tới địa điểm ~c~ thì có thể đi từ ~a~ đến ~c~. Hãy cho biết cần xây dựng ít nhất bao nhiêu đường đi trực tiếp giữa 2 địa điểm để kết nối ~m~ cặp địa điểm cho trước.

Nói tóm lại, từ đồ thị được cho ban đầu, hãy tìm cách giữ lại ít cạnh nhất sao cho số vùng liên thông được giữ nguyên.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m \le 10^5~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 địa điểm ~u, v \le n~.

Output

• In ra một số ~p~ là số lượng đường đi trực tiếp giữa 2 địa điểm.
• ~p~ dòng sau mỗi dòng in ra 2 số ~u, v~ nghĩa là xây đường đi giữa 2 địa điểm ~u~ và ~v~.
• Nếu có nhiều đáp án thỏa mãn, bạn có thể in ra đáp án bất kì.

Sample Test 1

Input:

4 2
1 2
1 4

Output:

2
1 2
2 4

Sample Test 2

Input:

4 3
1 2
2 3
3 1

Output:

1 2
1 3

Có ~n~ học sinh trong lớp của Uolevi, và ~m~ tình bạn giữa họ. Nhiệm vụ của bạn là chia học sinh thành hai đội theo cách mà không có hai học sinh nào trong một đội là bạn bè. Bạn có thể thoải mái lựa chọn kích thước của các đội.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~m~: số lượng học sinh và tình bạn. Các học sinh được đánh số ~1,2,\ldots,n~.
• Sau đó, có ~m~ dòng mô tả các tình bạn. Mỗi dòng có hai số nguyên ~a~ và ~b~: học sinh ~a~ và ~b~ là bạn bè.
• Mỗi tình bạn là giữa hai học sinh khác nhau. Bạn có thể giả định rằng có nhiều nhất một tình bạn giữa bất kỳ hai học sinh nào.

Output

• In một ví dụ về cách xây dựng các nhóm. Đối với mỗi học sinh, in ~1~ hoặc ~2~ tùy thuộc vào đội nào học sinh sẽ được chỉ định. Bạn có thể in bất kỳ đội hợp lệ nào.
• Nếu không có giải pháp nào, hãy in IMPOSSIBLE.

Constraints

• ~1 \leq n \leq 10 ^ 5~
• ~1 \leq m \leq 2 \cdot 10 ^ 5~
• ~1 \leq a, b \leq n~

Example

Sample input

5 3
1 2
1 3
4 5

Sample output

1 2 2 1 2

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này. Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm ~N (1 < N \leq 700)~ hàng và ~M (1 \leq M \leq 700)~ cột. Mỗi phần tử của ma trận là độ cao ~H_{ij}~ so với mặt nước biển ~(0 \leq H_{ij} \leq 10000)~ của ô ~(i,j)~. Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là ~1~ hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ ~X~ không quá ~1~ và chênh lệch tọa độ ~Y~ không quá ~1~.

Input

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách: ~N~ và ~M~
• Dòng 2 ~\ldots~ N + 1: Dòng ~i+1~ mô tả hàng ~i~ của ma trận với ~M~ số nguyên cách nhau bởi dấu cách: ~H_{ij}~

Output

• Một số nguyên duy nhất là số lượng đỉnh đồi.

• Example

Input 1

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0    
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0 

Output 1

3

Trên bảng kích thước ~n \times m~, máy tính chọn ngẫu nhiên một số ô là hang rắn được kí hiệu bởi kí tự ~+~. Người chơi cần di chuyển từ vị trí là ô chứa kí tự P đến ô chứa kí tự C. Một cách di chuyển được gọi là thông minh nếu càng tránh xa các ô là hang rắn càng tốt. Khoảng cách hai ô ~(x,y)~ và ~(u,v)~ được tính theo khoảng cách Manhattan: ~|x-u|+|y-v|~. Yêu cầu: Tìm cách di chuyển để trong quá trình di chuyển khoảng cách tới ô là hang rắn ngắn nhất là xa nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(n,m \le 2000)~.
• Tiếp theo là ~m~ hàng, mỗi hàng chứa kí tự là một trong các kí tự: ~'+'~ (hang rắn), ~'P'~ (xuất phát), ~'C'~ (đích), ~'.'~ (ô tự do).

Output

• Gồm một dòng chứa một số là khoảng cách tìm được.

Sample Input 1

4 5
P....
.....
+++..
....C

Sample Output 1

2

Trung và FireGhost đã bị phù thủy xấu xa Lihwy nhốt vào mê cung!

Mê cung là một đồ thị gồm ~n~ phòng, các phòng được nối với nhau bởi các mật đạo; biết giữa hai căn phòng chỉ có tối đa một mật đạo, và không tồn tại mật đạo nối một căn phòng với chính nó. Hiện tại, Trung và FireGhost đang ở phòng ~1~, và để thoát ra ngoài, họ cần phải đi đến phòng ~n~. Tuy nhiên, mỗi căn phòng đều có một con quái vật đáng sợ đang chờ họ sẵn, biết con quái vật trong phòng thứ ~i~ có sức mạnh ~a_i~.

Giữa lúc đang đau khổ, thần đèn Alànhddin xuất hiện và ban cho Trung và FireGhost một thanh kiếm với sức mạnh tuỳ ý để đánh bại đám quái vật! Nếu 2 người chọn thanh kiếm có sức mạnh ~x~, họ có thể đánh bại toàn bộ quái vật có sức mạnh không vượt quá ~x~; ngược lại, họ sẽ bị con quái vật đó nuốt chửng.

Tuy nhiên, Alànhddin là một kẻ tư bản: nếu Trung và FireGhost sử dụng thanh kiếm có sức mạnh là ~x~ và số quái vật mà Trung và FireGhost cần phải tiêu diệt ít nhất để đến căn phòng ~n~ là ~y~, họ sẽ phải trả cho Alànhddin số tiền là ~|x - y|~. Hãy giúp Trung và FireGhost chọn thanh kiếm có sức mạnh phù hợp để số tiền phải trả là ít nhất có thể nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~m~ (~1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5~) — lần lượt là số phòng và số mật đạo trong mê cung.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) — sức mạnh của con quái vật trong căn phòng thứ ~i~.

~m~ dòng tiếp theo, dòng thứ ~j~ gồm ~2~ số nguyên dương ~u_j, v_j~ (~1 \le u_j, v_j \le n~) thể hiện một mật đạo nối ~2~ căn phòng ~u_j~ và ~v_j~.

Output

Một số nguyên duy nhất là đáp án của bài toán: số tiền ít nhất mà Trung và FireGhost phải trả. Nếu Trung và FireGhost không thể đến được căn phòng ~n~, in ra đáp án ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

1

Sample Input 2

2 0
1 2

Sample Output 2

-1

Notes

Trong test ví dụ thứ nhất, khi đi từ ~1~ đến ~4~, bạn phải lần lượt đánh bại ~3~ con quái vật có sức mạnh ~1~, ~4~, ~2~. Nếu thanh kiếm có sức mạnh là ~4~, Trung và FireGhost sẽ có thể đến được căn phòng ~4~ với chi phí là ~|4-3| = 1~. Vậy đáp án là ~1~.

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Công việc này chưa bao giờ là dễ dàng. Một vài ô đã bị địch cài bom và không biết khi nào sẽ phát nổ. Bạn chỉ biết rằng loại bom này có sức công phá là ~r~, có nghĩa là nếu bom ở ô ~(i,j)~, khi nó phát nổ thì các ô ~(u,v)~ thỏa mãn ~|i-u| + |j-v| \le r~ sẽ bị tàn phá (ô ~(i,j)~ và ~(u,v)~ đều nằm trong bảng). Những ô ~(u,v)~ như vậy gọi là những ô bị ảnh hưởng bởi bom.

Đây là tài liệu mật, tất nhiên chỉ huy của bạn không muốn nhận một sự rủi ro nào, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) =~ ., nếu đây là một ô bình thường có thể đi.
• ~c(i,j) =~ *, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) =~ +, đây là ô có bom, như đã nói, các ô nằm cách ô này khoảng cách không quá ~r~ (kể cả chính nó) sẽ không thể đi vào.
• ~c(i,j) =~ S, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) =~ T, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.
  
  

Input

• Dòng đầu tiên gồm ~3~ số nguyên ~n,m,r~, miêu tả kích thước bảng và vùng ảnh hưởng của bom.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.
• Dữ liệu luôn đảm bảo ô chứa kí tự ~S~ và ~T~ không bị ảnh hưởng bởi ô chứa bom nào.
  
  

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy sao cho không được đi qua ô nào bị ảnh hưởng bởi bom. Nếu không có một đường đi nào như vậy, in ra ~-1~.
  
  

Constraints

• ~1 \le n,m \le 1000~
• ~0 \le r \le 1000~
  
  

Subtasks

• ~20\%~ số điểm: Không có ô nào có ~c(i,j) = *~ hoặc ~c(i,j) = +~.
• ~20\%~ số điểm: ~r = 0~.
• ~30\%~ số điểm: ~n,m \le 100~.
• ~30\%~ số điểm: Không có ràng buộc gì thêm.
  
  

Sample Test 1

Input:

3 4 1
S...
....
...T

Output:

5

Sample Test 2

Input:

3 4 0
S.+T
*.*.
*...

Output:

7

Sample Test 3

Input:

4 4 1
S..*
*...
+.*.
.T..

Output:

8