UVa Q321

//UVa Q321
#include <bits/stdc++.h>
using namespace std;

int r,d,s;
bool pass[11][11];
bool ctrl[11][11];//ctrl[a][b] := a control b room light
bool vis[1<<11][11];

struct status{
    int cur, loc;
};
status pre[1<<11][11];//for back trace usage

int32_t main(){
    int cnt = 0;
    while(cin >> r >> d >> s){
        if(r == 0 && d == 0 && s == 0)break;
        memset(pass, 0, sizeof(pass));
        memset(ctrl, 0, sizeof(ctrl));
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < d; ++i){
            int a,b;
            cin >> a >> b;
            pass[a][b] = pass[b][a] = 1;
        }
        for(int i = 0; i < s; ++i){
            int a,b;
            cin >> a >> b;
            if(a != b)ctrl[a][b] = 1;//a control b
        }
        //bfs
        deque<status> dq;
        status T={.cur = (1<<1), .loc = 1};
        vis[T.cur][T.loc] = 1;
        dq.emplace_back(T);
        bool fnd = 0;
        while(!dq.empty() && !fnd){
            T = dq.front();
            dq.pop_front();
            if(T.cur == (1<<r)){
                fnd = 1;
                break;
            }
            //////////////////////////////////
            //printf("%o %d\n", T.cur, T.loc);
            for(int i = 1; i <= r; ++i){
                if(!vis[T.cur][i] && pass[T.loc][i] && (T.cur & (1 << i))){//move
                    status tmd={.cur = T.cur, .loc = i};
                    pre[tmd.cur][tmd.loc] = T;
                    vis[tmd.cur][tmd.loc] = 1;
                    dq.emplace_back(tmd);
                    if(tmd.cur == (1<<r)){
                        fnd = 1;
                        break;
                    }
                }
                int nxt = T.cur ^ (1 << i);
                if(!vis[nxt][T.loc] && ctrl[T.loc][i] && !vis[nxt][T.loc]){//switch
                    status tmd{.cur = nxt, .loc = T.loc};
                    pre[tmd.cur][tmd.loc] = T;
                    vis[tmd.cur][tmd.loc] = 1;
                    dq.emplace_back(tmd);
                    if(tmd.cur == (1<<r)){
                        fnd = 1;
                        break;
                    }
                }
            }
            //////////////////////////////////
        }
        cout << "Villa #" << ++cnt << '\n';
        if(fnd){
            vector<status> v;
            status U{.cur = (1<<r), .loc = r};
            while(U.cur != 1<<1){
                v.emplace_back(U);
                U = pre[U.cur][U.loc];
            }
            cout << "The problem can be solved in " << v.size() << " steps:\n";
            while(!v.empty()){
                T = v.back();//U => T
                if(U.loc != T.loc){
                    cout << "- Move to room " << T.loc << ".\n";
                }else{
                    int k = 0;
                    while((T.cur & (1 << k)) == (U.cur & (1 << k)))++k;
                    if(U.cur & (1 << k))cout << "- Switch off light in room " << k << ".\n";
                    else cout << "- Switch on light in room " << k << ".\n";
                }
                U = T;
                v.pop_back();
            }
        }else{
            cout << "The problem cannot be solved.\n";
        }
        cout << '\n';
    }
    return 0;
}