#include <iostream>

using namespace std;

int NrCif(int n)
{
    int nr=0;
    if(n==0) return 1;
    while(n)
    {
        nr++;
        n/=10;
    }
    return nr;
}

void Constr(int &n,int &t,int &m,int v[],int &nrel,int a[][3])
{
    cin>>n>>t>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i][1]>>a[i][2];
    nrel=NrCif(n);
    for(int i=nrel;i>0;i--)
    {
        v[i]=n%10;
        n/=10;
    }
}

void Intersc(int &x,int &y)
{
    if(x*y!=0)
    {
        int aux=x;
        x=y;
        y=aux;
    }
}

void Trs(int v[],int n,int a[][3],int m)
{
    for(int i=1;i<=m;i++)
        Intersc(v[a[i][1]],v[a[i][2]]);
}

int NrFin(int v[],int n)
{
    int x=0;
    for(int i=1;i<=n;i++)
        x=x*10+v[i];
    return x;
}


int main()
{
    int n,m,t,nrel,v[11],a[11][3];

    Constr(n,t,m,v,nrel,a);
    for(int i=1;i<=t;i++)
        Trs(v,nrel,a,m);
    cout<<NrFin(v,nrel);


    return 0;
}