#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int N=60*20*60*6,INF=0xffffff;
int n,m;
int U[N],D[N],L[N],R[N];
int row[N],col[N];
int S[N],H[N],ans[N];
int siz;
int node[66][66],mp[66][66];
int st[66],et[66],a,d,num,np[6][6];
int ans1[N],ans2[N],nps[N],npe[N];

/*
int mas[4444][4444];
void print()
{
    memset(mas,0,sizeof(mas));
    for(int i=m+1;i<siz;i++)
    {
        mas[row[i]][col[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(i%num==0) cout<<endl;
        cout<<i%num<<": \t";
        for(int j=1;j<=m;j++)
        {
            cout<<mas[i][j];
            if(j%d==a) cout<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
*/
void init()
{
    for(int i=0;i<=m;i++)
    {
        L[i]=i-1;
        R[i]=i+1;
        col[i]=i;
        U[i]=D[i]=i;
        row[i]=-1;
    }
    R[m]=0;
    L[0]=m;
    siz=m+1;
    memset(H,0,sizeof(H));
    memset(S,0,sizeof(S));
    S[0]=INF+1;
}

void insert(int r,int c)
{
    U[siz]=U[c];
    D[siz]=c;
    U[D[siz]]=siz;
    D[U[siz]]=siz;
    if(H[r])
    {
        L[siz]=L[H[r]];
        R[siz]=H[r];
        L[R[siz]]=siz;
        R[L[siz]]=siz;
    }
    else H[r]=L[siz]=R[siz]=siz;
    row[siz]=r;
    col[siz]=c;
    S[c]++;
    siz++;
}

void build()
{
    init();
    for(int i=0;i<a;i++)
    {
        int s,e,j;
        insert(i*num,i+1);
        for(s=st[i];s<=et[i];s++)
        {
            for(e=s;e<=et[i];e++)
            {
                for(j=s;j<=e;j++)
                {
                    insert(i*num+np[s][e],a+i*d+j+1);
                    for(int k=1;k<node[i][0];k++) insert(i*num+np[s][e],a+node[i][k]*d+j+1);
                }
                insert(i*num+np[s][e],i+1);
            }
        }
    }
}

void remove(int c)
{
    L[R[c]]=L[c];
    R[L[c]]=R[c];
    for(int i=D[c];i!=c;i=D[i])
    {
        for(int j=R[i];j!=i;j=R[j])
        {
            U[D[j]]=U[j];
            D[U[j]]=D[j];
            S[col[j]]--;
        }
    }
}

void resume(int c)
{
    for(int i=U[c];i!=c;i=U[i])
    {
        for(int j=L[i];j!=i;j=L[j])
        {
            D[U[j]]=j;
            U[D[j]]=j;
            S[col[j]]++;
        }
    }
    R[L[c]]=c;
    L[R[c]]=c;
}

bool dfs(int k)
{
    if(R[0]==0) return true;
    int mins=INF,c=0;
    for(int t=R[0];t!=0;t=R[t])
    {
        if(S[t]<mins)
        {
            mins=S[t];
            c=t;
        }
    }
    if(c==0) return false;
    remove(c);
    for(int i=D[c];i!=c;i=D[i])
    {
        ans[k]=row[i];
        for(int j=R[i];j!=i;j=R[j]) remove(col[j]);
        if(dfs(k+1)) return true;
        for(int j=L[i];j!=i;j=L[j]) resume(col[j]);
    }
    resume(c);
    return false;
}

int main()
{
    int b;
    ios::sync_with_stdio(false);
    while(scanf("%d %d %d",&a,&b,&d)==3)
    {
        int i,j,k;
        num=d*(d+1)/2+1;
        n=a*num;
        m=a*d+a;
        for(k=1,i=0;i<d;i++) for(j=i;j<d;j++) np[i][j]=k++;
        memset(mp,0,sizeof(mp));
        for(i=0;i<b;i++)
        {
            scanf("%d %d",&j,&k);
            j--;k--;
            if(j<k) swap(j,k);
            mp[j][k]=1;
        }
        for(i=0;i<a;i++) node[i][0]=1;
        for(j=0;j<a;j++) for(k=0;k<a;k++) if(mp[j][k])
        {
            node[j][node[j][0]++]=k;
            node[k][node[k][0]++]=j;
        }
        for(i=0;i<a;i++)
        {
            scanf("%d %d",&st[i],&et[i]);
            st[i]--;et[i]--;
        }
        build();
        //print();
        if(!dfs(0))
        {
            puts("No solution\n");
            continue;
        }
        for(i=0;i<a;i++)
        {
            j=ans[i]%num;
            if(j){for(int s=0;s<d;s++) for(int e=s;e<d;e++) if(np[s][e]==j){ans1[ans[i]/num]=s+1;ans2[ans[i]/num]=e+1;}}
            else{ans1[ans[i]/num]=ans2[ans[i]/num]=0;}
        }
        for(i=0;i<a;i++) printf("%d %d\n",ans1[i],ans2[i]);
        puts("");
    }
    return 0;
}