Khám phá tầng hầm

Michael tham gia một chuyến tham quan một tòa lâu đài cổ. Lâu đài này có một tầng hầm gồm N căn phòng (được đánh số từ 1 đến N) được kết nối với nhau bởi M hành lang. Trong đó, phòng số 1 là căn phòng đầu tiên khi bước vào và phòng số N là căn phòng cuối cùng trước khi rời khỏi tầng hầm. Vì trong tầng hầm hoàn toàn không có ánh sáng, để có thể bước vào bất kỳ căn phòng nào thì đèn của phòng đó phải được bật sáng từ trước. Ban đầu khi Michael bước vào phòng 1, đèn của phòng này đã được bật sẵn.

Hệ thống công tắc của các phòng cũng khá đặc biệt. Công tắc đèn của một phòng có thể được đặt tại một căn phòng khác. Ví dụ, công tắc của phòng số 3 được đặt ở phòng số 1, nhưng công tắc của phòng số 1 chưa chắc đã nằm ở phòng số 3 mà có thể nằm ở phòng số 2.

Trước khi xuống tầng hầm, Michael nhận được một tấm bản đồ bao gồm các lối đi giữa các phòng và hệ thống công tắc đèn. Hãy giúp Michael tìm phương án di chuyển từ phòng đầu tiên (phòng số 1) đến phòng cuối cùng (phòng số N) của tầng hầm sao cho tốn ít thời gian nhất mà vẫn đảm bảo tiết kiệm điện (khi rời khỏi tầng hầm qua phòng số N, chỉ duy nhất đèn của phòng số N được bật).

Lưu ý rằng mỗi lượt di chuyển giữa hai phòng hoặc mỗi thao tác bật/tắt đèn đều tốn một đơn vị thời gian.

Đầu vào: Dòng đầu tiên chứa ba số nguyên N, M và K cách nhau bởi dấu cách — lần lượt là số lượng phòng, số lượng hành lang và số lượng công tắc đèn.

M dòng tiếp theo, mỗi dòng chứa hai số nguyên r_i và r_j cách nhau bởi dấu cách, cho biết có một hành lang nối giữa phòng r_i và phòng r_j.

K dòng tiếp theo, mỗi dòng chứa hai số nguyên s và r cách nhau bởi dấu cách, cho biết khi đứng ở phòng s có thể bật/tắt đèn của phòng r.

Ràng buộc:

• $1 \leq N \leq 20$
• $1 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq K \leq N(N - 1)$
• $1 \leq r_i, r_j \leq N$, $r_i \neq r_j$
• $1 \leq s, r \leq N$, $s \neq r$

Đầu ra: Nếu không tồn tại phương án hợp lệ, in ra một dòng duy nhất chứa chuỗi NO SOLUTION.

Nếu có phương án, in ra phương án tốn ít thời gian nhất theo định dạng dưới đây:

• Mỗi dòng là một lượt di chuyển hoặc một thao tác bật/tắt đèn.
• Nếu là lượt di chuyển, dòng đó có định dạng M x với x là số hiệu của căn phòng di chuyển tới.
• Nếu là thao tác bật/tắt đèn, dòng đó có định dạng S x1 x2 x3 ... với x1, x2, x3, ... là số hiệu của các phòng được bật hoặc tắt đèn trong thao tác đó.

Giải thích: Trong ví dụ này, các mũi tên màu xanh lá thể hiện lối đi giữa các phòng, còn các mũi tên màu đỏ thể hiện vị trí công tắc điều khiển đèn của các phòng.

Ví dụ 1:

Đầu vào:

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

Đầu ra:

S 2
M 2
S 3
M 1
S 2
M 3
S 4
M 4
S 1 3