#include <cstdio>#include <cstring>using namespace std;const int HashSize = 2000000;const int MAXN = 300000;const char action[][50] = {"- Move to room ", "- Switch off light in room ", "- Switch on light in room "}; typedef int State[11];State qu[MAXN];int head[HashSize], next[HashSize];int room[11][11], swit[11][11], roomNum;int father[MAXN], ans, step[MAXN];char path[MAXN][35];inline void BFS();inline bool TryToInsert(int s);inline bool IsOk(State &cur);inline void Init();inline bool Go(State &curState, int curLoca, int tarGet, int way);inline int BKDHash(State &s);inline void PrintPath(int cur);int main(){//freopen("input.txt", "r", stdin);int d, s, i, j, a, b, cases = 1;while (scanf("%d%d%d", &roomNum, &d, &s), roomNum + d + s){memset(room, 0, sizeof(room));memset(swit, 0, sizeof(swit));for (i = 0; i < d; i++){scanf("%d%d", &a, &b);room[a][b] = room[b][a] = 1;}for (i = 0; i < s; i++){scanf("%d%d", &a, &b);swit[a][b] = 1;}BFS();printf("Villa #%dn", cases++);if (ans != -1){printf("The problem can be solved in %d steps:n", step[ans]);PrintPath(ans);}elseprintf("The problem cannot be solved.n");printf("n");}return 0;}inline void BFS(){int i, j;Init();int front = 0, rear = 1;while (front < rear){State &curState = qu[front];if (IsOk(curState)){ans = front;return;}int curLoca;for (i = 1; i <= roomNum; i++)if (curState[i] == 2){curLoca = i;break;}for (i = 1; i <= roomNum; i++){if (i != curLoca){for (int j = 0; j < 3; j++){State &t = qu[rear];memcpy(t, curState, sizeof(curState));if (Go(t, curLoca, i, j))if (TryToInsert(rear)){father[rear] = front;step[rear] = step[front] + 1;char str[4]; if (i < 10)str[0] = i + '0', str[1] = '.', str[2] = 0;if (i == 10)str[0] = '1', str[1] = '0', str[2] = '.', str[3] = 0;strcpy(path[rear], action[j]);strcat(path[rear], str);rear++;}}}}front++;}ans = -1;}inline bool TryToInsert(int s){int h = BKDHash(qu[s]);int u = head[h];while (u){if (memcmp(qu[u], qu[s], sizeof(qu[h])) == 0)return 0;u = next[u];}next[s] = head[h];head[h] = s;return 1;}inline int BKDHash(State &s){int seed = 131;int Hash = 0;for (int i = 1; i <= roomNum; i++)Hash = Hash * seed + s[i];return (Hash & 0x7FFFFFFF) % HashSize;}inline bool IsOk(State &cur){int i;for (i = 1; i < roomNum; i++)if (cur[i])return false;if (cur[i] == 2)return true;return false;}inline bool Go(State &curState, int curLoca, int tarGet, int way){if (way == 0){if (room[curLoca][tarGet] && curState[tarGet]){curState[tarGet] = 2; curState[curLoca] = 1;return true;}}else if (way == 1){if (swit[curLoca][tarGet] && curState[tarGet]){curState[tarGet] = 0;return true;}}else if (way = 2){if (swit[curLoca][tarGet] && !curState[tarGet]){curState[tarGet] = 1;return true;} }return false;}inline void Init(){memset(head, 0, sizeof(head));memset(qu, 0, sizeof(qu));qu[0][1] = 2;father[0] = -1, step[0] = 0;}inline void PrintPath(int cur){if (father[cur] != -1){PrintPath(father[cur]);printf("%sn", path[cur]);}}
