Bạn được cho một bản đồ hình chữ nhật biểu diễn mê cung.
Mỗi ô có thể là:

• tường (#)
• ô trống (.)
• vị trí bắt đầu (A)
• vị trí đích (B)

Bạn cần tìm đường đi ngắn nhất từ A đến B.
Các bước di chuyển chỉ được phép theo 4 hướng: lên, xuống, trái, phải.
Nếu tồn tại đường đi, hãy in ra độ dài đường đi và chuỗi các bước di chuyển.
Nếu không có đường đi, in ra NO.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên n và m: kích thước của mê cung.
• Sau đó là n dòng, mỗi dòng gồm m ký tự mô tả mê cung:
  • #: tường
  • .: ô trống
  • A: vị trí bắt đầu
  • B: vị trí đích

Dữ liệu ra:

Nếu tồn tại đường đi:

• In ra YES
• In ra độ dài đường đi (một số nguyên)
• In ra chuỗi mô tả các bước đi, gồm các ký tự U, D, L, R.

Nếu không tồn tại đường đi:

• In ra NO

Input:

5 8
########
#.A#...#
#.##.#B#
#......#
########

Output:

YES
9
LDDRRRRRU

Giới hạn:

• 1 ≤ n, m ≤ 1000

Byteland có ~n~ thành phố và ~m~ con đường nối giữa chúng. Mục tiêu là xây dựng thêm một số con đường mới sao cho mọi cặp thành phố đều có thể đi đến nhau (tức là đồ thị trở nên liên thông).

Nhiệm vụ của bạn là xác định số lượng tối thiểu các con đường cần xây thêm và liệu kê những con đường này.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: số lượng thành phố và số lượng con đường hiện có.
• Sau đó có ~m~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~ — cho biết có một con đường giữa hai thành phố đó.

Mỗi con đường nối hai thành phố khác nhau, và không có hai con đường nào trùng nhau.

Dữ liệu ra:

• In ra một số nguyên ~k~: số lượng con đường cần xây thêm.
• Sau đó in ra ~k~ dòng, mỗi dòng chứa hai số nguyên mô tả các con đường mới.

Có thể in ra bất kỳ lời giải hợp lệ nào.

Input:

4 2
1 2
3 4

Output:

1
2 3

Giới hạn:

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

Mạng máy tính của Syrjälä có ~n~ máy tính và ~m~ kết nối giữa chúng. Các máy tính được đánh số từ ~1~ đến ~n~. Máy tính của Uolevi là ~1~, máy tính của Maija là ~n~.

Nhiệm vụ của bạn là xác định xem Uolevi có thể gửi tin nhắn đến Maija hay không. Nếu có thể, hãy tìm độ dài ngắn nhất của đường đi (tính theo số lượng máy tính trên đường đó), và in ra một ví dụ cụ thể của đường đi này.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: số lượng máy tính và số lượng kết nối.
• Sau đó có ~m~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~, biểu thị rằng có một kết nối giữa hai máy tính đó.

Mỗi kết nối luôn nối hai máy tính khác nhau, và không có hai kết nối nào trùng nhau.

Dữ liệu ra:

Nếu có thể gửi tin nhắn:

• Dòng đầu tiên in ra số nguyên ~k~: số lượng máy tính trên đường đi ngắn nhất.
• Dòng thứ hai in ra một ví dụ đường đi hợp lệ (liệt kê các chỉ số máy tính theo thứ tự).

Nếu không có đường đi, in ra IMPOSSIBLE.

Input:

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

Output:

3
1 4 5

Giới hạn:

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

Lớp học của Uolevi có ~n~ học sinh và ~m~ mối quan hệ bạn bè giữa họ.

Nhiệm vụ của bạn là chia các học sinh thành hai đội sao cho không có hai bạn cùng đội nào là bạn của nhau. Kích thước của hai đội có thể tùy ý.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: số lượng học sinh và số lượng mối quan hệ bạn bè.
• Sau đó có ~m~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~, cho biết học sinh ~a~ và ~b~ là bạn bè.

Mỗi mối quan hệ bạn bè là giữa hai học sinh khác nhau, và không có hai mối quan hệ trùng nhau.

Dữ liệu ra:

• In ra ~n~ số nguyên, mỗi số là ~1~ hoặc ~2~, cho biết đội mà học sinh đó được xếp vào.

Nếu có nhiều cách chia hợp lệ, có thể in ra bất kỳ cách chia hợp lệ nào. Nếu không thể chia được, in ra IMPOSSIBLE.

Input:

5 3
1 2
1 3
4 5

Output:

1 2 2 1 2

Giới hạn:

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

Đất nước X có ~n~ thành phố được đánh số ~1, 2,\dots, n~ và ~m~ con đường nối giữa các thành phố. Bạn hãy thiết kế một chuyến đi khứ hồi bắt đầu ở một thành phố, đi tới hai hoặc nhiều thành phố khác nhau và cuối cùng quay trở về thành phố đầu tiên. Mọi thành phố trong chuyến đi phải là phân biệt.

Dữ liệu vào:

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1\leq n\leq 10^5; 1\leq m\leq 2\times 10^5)~: số thành phố và con đường.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1\leq u, v\leq n; u\neq v)~: tồn tại đường đi giữa hai thành phố ~u~ và ~v~.

Dữ liệu đảm bảo có tối đa một đường đi giữa hai thành phố bất kỳ.

Dữ liệu ra:

In ra một số nguyên ~k~ là số thành phố trong chuyến đi. Dòng tiếp theo in ra ~k~ thành phố theo thứ tự chuyến đi.

Bạn có thể in bất kỳ chuyến đi nào thỏa mãn.

Nếu không có chuyến đi khứ hồi, in ra IMPOSSIBLE.

Input:

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

Output:

4
3 5 1 3