uva 321 WA

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <cstring>
#include <functional>
#include <iterator>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <sstream>
#include <queue>
#include <deque>
#include <list>
#include <stack>
using namespace std;
// printing
#ifdef _DEBUG
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); _dbg(_it, args); }
void _dbg(istream_iterator<string> it){++it;}
template<typename T, typename... Args>
void _dbg(istream_iterator<string> it, T a, Args... args){
  if (*it=="'\\n'" || *it=="\"\\n\"" || *it=="endl") { cout << "\n"; }
  else { cout << setw(8) << std::left << *it << " = " << setw(4) << std::right << a << "\n"; }
  _dbg(++it, args...); }
template<typename T>
std::ostream& _containerprint(std::ostream &out, T const &val) { return (out << setw(4) << val << " "); }
template<typename T1, typename T2>
std::ostream& _containerprint(std::ostream &out, std::pair<T1, T2> const &val) { return (out << "{" << setw(4) << val.first << " " << setw(4) << val.second << "} "); }
template<template<typename, typename...> class TT, typename... Args>
std::ostream& operator<<(std::ostream &out, const TT<Args...> &cont) { for(auto&& elem : cont) { _containerprint(out, elem); } return out; }
std::ostream& operator<<(std::ostream &out, const std::string &s) { return operator << <char>(out, s); }
#endif
// other
#define endl '\n'
#define all(v) begin(v), end(v)
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> ii;
typedef std::vector<ii> vii;
typedef std::vector<int> vi;
const double EPS = 1e-9;
const int mod = 998244353;
template<typename T> T gcd(T a, T b){T c; while(b){c=b; b=a%b; a=c;} return a;}
template<typename T> T powmod(T a, T b){T res = 1; a %= mod; while(b){if(b&1)res=res*(a%mod); a=a*(a%mod); b>>=1;} return res;}






int V, E, S;
vector<int> G[12];
vector<int> light[12];

int dist[12][1025];
ii pre[12][1025];

void bfs(ii ts) {
  queue<ii> q;
  dist[ts.first][ts.second] = 0;
  q.push(ts);
  while (!q.empty()) {
    ts = q.front(); q.pop();
    int u = ts.first, bm = ts.second;
    for (int l : light[u]) {
      int bm1 = bm ^ (1 << l);
      if ((bm1 & (1 << u)) && dist[u][bm1] == -1) {
        dist[u][bm1] = dist[u][bm] + 1;
        pre[u][bm1] = ii(u, bm);
        q.emplace(u, bm1);
      }
    }
    for (int v : G[u]) {
      if ((bm & (1 << v)) && dist[v][bm] == -1) {
        dist[v][bm] = dist[u][bm] + 1;
        pre[v][bm] = ii(u, bm);
        q.emplace(v, bm);
      }
    }
  }
}

void Solve() {
  int TC = 1;
  while (cin >> V >> E >> S, V != 0 || E != 0 || S != 0) {
    if (TC > 1) cout << endl;
    for (int u = 0; u < 12; ++u) G[u].clear(), light[u].clear();
    memset(dist, -1, sizeof(dist));
    for (int i = 0; i < E; ++i) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      G[u].push_back(v);
      G[v].push_back(u);
    }
    for (int i = 0; i < S; ++i) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      light[u].push_back(v);
    }

    pre[0][1] = {-1, -1};
    bfs(ii(0, 1));

    cout << "Villa #" << TC++ << "\n";
    int u = V-1, bm = 1 << (V-1);
    if (dist[u][bm] == -1) {
      cout << "The problem cannot be solved.\n";
    } else {
      cout << "The problem can be solved in " << dist[u][bm] << " steps:\n";
      vector<string> ans;
      while (u != -1) {
        int pu = pre[u][bm].first, pbm = pre[u][bm].second;
        if (pu == u) {
          int diff = __builtin_ffs(bm ^ pbm); //position of lsb (1-indexed)
          if (bm & (1 << diff)) ans.push_back("- Switch off light in room " + to_string(diff) + ".");
          else ans.push_back("- Switch on light in room " + to_string(diff) + ".");
        } else {
          ans.push_back("- Move to room " + to_string(u+1) + ".");
        }
        u = pu, bm = pbm;
      }
      for (int i = ans.size()-2; i >= 0; --i) {
        cout << ans[i] << endl;
      }
    }
  }
}


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  #ifdef _DEBUG
//  std::freopen("in.txt", "r", stdin);
//  std::freopen("out.txt", "w", stdout);
  #endif
  Solve();
}