#include <iostream>

#include<map>

#include<memory.h>

#include<stdio.h>

#include<string>

#include<queue>

#include<vector>

using namespace std;

const int  MAXN = ;

class Node

{

public:

    vector<string>step;

    int cur;

    int curStepNum;

    int lights;

    Node()

    {

        //step.reserve(65535);

    }

    bool operator <(const Node& node) const

    {

        return curStepNum > node.curStepNum;

    };

};

int conn[MAXN][MAXN];

int contro[MAXN][MAXN];

int r, d, s;

int states[][];

priority_queue<Node>q;

int perLights[] = {

     << , << , <<  , <<  , <<  , <<  ,

     << , << , <<  , <<  };

void read()

{

    int ss, ee;

    for (int i = ;i < d;i++)

    {

        cin >> ss >> ee;

        //start with 0

        conn[ss - ][ee - ] = ;

        conn[ee - ][ss - ] = ;

    }

    for (int i = ;i < s;i++)

    {

        cin >> ss >> ee;

        contro[ss - ][ee - ] = ;

    }

}

Node bfs()

{

    Node node;

    node.cur = ;

    node.curStepNum = ;

    node.lights = ;

    q.push(node);

    //init node 只有0房间是亮的

    states[][] = ;

    while (q.empty() == false)

    {

        node = q.top();

        q.pop();

        int curIndex = node.cur;

        //cur lights state

        int curLights = node.lights;

        int curStepNum = node.curStepNum;

        //判断是不是终点

        if ((curIndex == r - ) && curLights == perLights[r - ])

        {

            return node;

        }

        //枚举灯的状态

        for (int i = ;i < ; i++)

        {

            if (contro[curIndex][i] == )

                continue;

            if (i == curIndex)

                continue;

            //控制的灯

            int nextControLightIndex = i;

            string desc = "";

            int nextLight = ;

            if ((curLights & perLights[nextControLightIndex]) == perLights[nextControLightIndex])

            {

                //关闭next房间的灯

                nextLight = (curLights ^ perLights[nextControLightIndex]);

                if (states[curIndex][nextLight] == )

                    //repeat

                    continue;

                desc = "- Switch off light in room " + std::to_string(nextControLightIndex + );

                desc += ".";

            }

            else

            {

                //打开next房间的灯

                nextLight = curLights | perLights[nextControLightIndex];

                if (states[curIndex][nextLight] == )

                    //repeat

                    continue;

                desc = "- Switch on light in room " + std::to_string(nextControLightIndex + );

                desc += ".";

            }

            Node newNode;

            newNode.curStepNum = curStepNum + ;

            newNode.cur = curIndex;

            newNode.lights = nextLight;

            newNode.step = node.step;

            newNode.step.push_back(desc);

            //push to queue

            q.push(newNode);

            states[curIndex][nextLight] = ;

        }

        //end curIndex enum lights state

        //start door

        for (int i = ;i < ;i++)

        {

            if (curIndex == i)

                continue;

            if (conn[curIndex][i] == )

                continue;

            int nextDoor = i;

            if ((perLights[nextDoor] & curLights) == )

                //灯是灭的,不能进

                continue;

            if (states[nextDoor][curLights] == )

                //已经看到过,不能进

                continue;

            //灯是开着的,能进

            Node newNode;

            newNode.cur = nextDoor;

            newNode.curStepNum = curStepNum + ;

            newNode.lights = curLights;

            newNode.step = node.step;

            string desc = "- Move to room " + std::to_string(nextDoor + );

            desc += ".";

            newNode.step.push_back(desc);

            states[nextDoor][curLights] = ;

            q.push(newNode);

        }

    }

    node.cur = -;

    return node;

}

int main()

{

    int t = ;

    while (cin >> r >> d >> s)

    {

        if (r == d && d == s && r == )

            break;

        memset(conn, , sizeof(conn));

        memset(contro, , sizeof(conn));

        memset(states, , sizeof(states));

        while (q.empty() == false)

            q.pop();

        read();

        cout << "Villa #";

        cout << t +  << endl;

        if (r == )

        {

            cout << "The problem can be solved in " <<  << " steps:" << endl;

        }

        else

        {

            Node node = bfs();

            //cout << "test" << endl;

            if (node.cur == -)

            {

                cout << "The problem cannot be solved." << endl;

            }

            else

            {

                cout << "The problem can be solved in " << node.curStepNum << " steps:" << endl;

                vector<string> b = node.step;

                for (int i = ;i <= b.size() - ;i++)

                    cout << b[i] << endl;;

            }

        }

        t++;

        cout << endl;

    }

}