DFS-BFS

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)
• Ràng buộc:
  • \(1 \leq n, m \leq 1000\)

Output

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

Example

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

3

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ỳ
• Ràng buộc:
  • \(1 \leq n \leq 10^5\)
  • \(1 \leq m \leq 2 \cdot 10^5\)
  • \(1 \leq a, b \leq n\)

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

Example

4 2
1 2
3 4

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

Constraints

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

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.

Example

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

3
1 4 5

Bài này là bản dễ hơn của: CSES - Labyrinth | Mê cung
Bạn được cho bản đồ của một mê cung, và nhiệm vụ của bạn là tìm đường đi từ A đến B. Bạn có thể đi một trong bốn hướng trái, phải, lên và xuống.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
• Sau đó, có \(n\) dòng gồm \(m\) ký tự mô tả mê cung. Mỗi ký tự là . (sàn), # (tường - không đi vào ô này), A (bắt đầu) hoặc B (kết thúc).

Output

• Đầu tiên in YES nếu có một đường đi và NO ngược lại.
• Nếu có một đường đi, in độ dài của đường đi đó và mô tả của nó dưới dạng một xâu bao gồm các ký tự L (trái), R (phải), U (lên) và D (xuống). Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

• \(1 \leq n, m \leq 1000\)

Example

Sample input

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

Sample output

YES
9
LDDRRRRRU

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

Constraints

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

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

Example

5 3
1 2
1 3
4 5

1 2 2 1 2

Byteland có \(n\) thành phố và \(m\) con đường giữa chúng. Nhiệm vụ của bạn là thiết kế một chuyến đi vòng tròn bắt đầu trong một thành phố, đi qua hai hoặc nhiều thành phố khác và cuối cùng trở về thành phố bắt đầu. Mỗi thành phố trung gian trên tuyến đường phải phân biệt.

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. 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ỗi con đường nằm giữa 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ỳ

Constraints

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

Output

• Đầu tiên in một số nguyên \(k\): số thành phố trên tuyến đường. Sau đó in \(k\) thành phố theo thứ tự chúng sẽ được truy cập. Bạn có thể in bất kỳ giải pháp hợp lệ nào
• Nếu không có giải pháp, hãy in IMPOSSIBLE

Example

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

4
3 5 1 3

Bạn và một số con quái vật đang ở trong một mê cung. Khi đi một bước theo một hướng nào đó trong mê cung, mỗi con quái vật cũng có thể đồng thời đi một bước theo một hướng nào đó. Mục tiêu của bạn là đến một trong những ô vuông ranh giới mà không bao giờ đi vào cùng ô với một con quái vật.

Nhiệm vụ của bạn là tìm hiểu xem mục tiêu của bạn có khả thi hay không, và nếu có, hãy in một đường đi mà bạn có thể đi theo. Kế hoạch của bạn phải hoạt động trong mọi tình huống; ngay cả khi những con quái vật biết trước đường đi của bạn.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
• Sau đó, có \(n\) dòng gồm \(m\) ký tự mô tả bản đồ. Mỗi ký tự là . (sàn), # (tường), A (bắt đầu) hoặc M (quái vật). Có chính xác một A trong đầu vào.

Output

• Trước tiên, hãy in YES nếu mục tiêu của bạn là có thể và NO nếu ngược lại.
• Nếu mục tiêu của bạn là có thể, hãy in ví dụ về đường đi hợp lệ (độ dài của đường đi và mô tả của đường đi bằng cách sử dụng các ký tự D, U, L và R).
• Bạn có thể in bất kỳ đường đi nào miễn là độ dài của nó nhiều nhất là \(n \cdot m\) bước.

Constraints

• \(1 \leq n, m \leq 10^3\)

Example

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

YES
5
RRDDR