/*

23

233

223

啦啦啦德玛西亚

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 1000007

using namespace std;

int n,m,ans;

char a[N];

int main()

{

    freopen("trans.in","r",stdin);

    freopen("trans.out","w",stdout);

    while(~scanf("%d%d%s",&n,&m,a))

    {

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

        {

            if(!m) break;

            if(a[i]=='' && a[i+]=='' && a[i+]=='')

            {

                if(i%==)

                {

                    if(m%==) break;

                    else

                    {

                        a[i+]='';

                        break;

                    }

                }

                else

                {

                    m--;

                    a[i+]='';

                    continue;

                }

            }

            else if(a[i]=='' && a[i+]=='' && a[i+]

=='')

            {

                if(i%==)

                {

                    a[i]='';

                    m--;

                    continue;

                }

                else

                {

                    if(m%==) break;

                    else

                    {

                        a[i+]='';

                        break;

                    }

                }

            }

            else if(a[i]=='' && a[i+]=='')

            {

                m--;

                if(i%) a[i]='';

                else a[i+]='';

            }

        }

        printf("%s",a);printf("\n");

    }

    fclose(stdin);fclose(stdout);

    return ;

}

/*

把豆豆和砖块丢在一起dp

f[i][j][k]:到第i行,蛇的长度还剩下j,从k位置出第i行的最大得分

g[j][l][r]:蛇的长度剩下j,从当前行l到r区间内仍为死亡的最大得分

初始化:对于每个i，g[j][k][k]=f[i-1][j-a[i][k]][k]+max(-a[i][k],0) 为初始状态

方程g[j][l][r] = max(g[j-a[i][l]][l+1][r] + max(-a[i][j],0),g[j-a[i][r]][l][r-1]+max(-a[i][k],0));

最后f[i][j][k] = max{g[j][l][r](1≤l≤k ≤r ≤5)}

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 207

#define M 10005

using namespace std;

int a[N][],f[N][M][],g[M][][];

bool flag[N][];

int n,m,maxi,ans,val;

inline int read()

{

    int x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int main()

{

    freopen("snakevsblock.in","r",stdin);

    freopen("snakevsblock.out","w",stdout);

    n=read();int x,y;

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

      a[i][j]=read();

    m=read();

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

    {

        x=read();y=read();

        flag[x][y-]=;

    }

    memset(f,-0x7f7f7f,sizeof f);

    f[][][]=;maxi=n*;

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

    {

        memset(g,-0x7f7f7f,sizeof g);

        for(int j=;j<=maxi;j++)

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

            if(j-a[i][k]>= && j-a[i][k]<=maxi)

              f[i][j][k]=g[j][k][k]=f[i-][j-a[i][k]][k]+max(-a[i][k],);

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

          for(int j=,k=j+l;k<;j++,k++)

            for(int v=;v<=maxi;v++)

            {

                if(!flag[i][j]  && (val=v-a[i][j])>= && val<=maxi) g[v][j][k] = g[val][j + ][k] + max(-a[i][j], );//g[v][j][k]=max(g[v][j][k],g[val][j+1][k]+max(-a[i][j],0));

                if(!flag[i][k-]&& (val=v-a[i][k])>= && val<=maxi) g[v][j][k]=max(g[v][j][k],g[val][j][k-]+max(-a[i][k],));

                for(int to=j;to<=k;to++) f[i][v][to]=max(f[i][v][to],g[v][j][k]);

            }

    }

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

      for(int j=;j<=maxi;j++)

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

          ans=max(f[i][j][k],ans);

    printf("%d\n",ans);

    return ;

}

#include <bits/stdc++.h>

using namespace std;

int n, m, P, u, v, to[200005], nxt[200005], p[100005], deep[100005], q[500005][2];

int son[100005], fa[100005], size[100005], top[100005], dfsx[100005], cnt, ans;

int lca[500005], Q[500005], lr[100005][2];

int sta[100005];

bool flag[400005];

void dfs(int x)

{

	size[x] = 1;

	for (int i = p[x]; i != -1; i = nxt[i])

		if (to[i] != fa[x])

		{

			fa[to[i]] = x;

			deep[to[i]] = deep[x] + 1;

			dfs(to[i]);

			if (son[x] == -1 || size[to[i]] > size[son[x]]) son[x] = to[i];

			size[x] += size[to[i]];

		}

}

void dfs1(int x)

{

	dfsx[x] = ++cnt;

	if (son[x] != -1) top[son[x]] = top[x], dfs1(son[x]);

	for (int i = p[x]; i != -1; i = nxt[i])

		if (to[i] != fa[x] && to[i] != son[x])

			top[to[i]] = to[i], dfs1(to[i]);

}

int findlca(int x, int y)

{

	while (1)

	{

		if (top[x] == top[y]) return deep[x] > deep[y]? y : x;

		if (deep[top[x]] > deep[top[y]]) x = fa[top[x]];

		else y = fa[top[y]];

	}

}

bool query(int x, int l, int r, int ll, int rr)

{

	if (l == ll && r == rr) return flag[x];

	int mid = (l + r) >> 1, L = x << 1, R = L | 1;

	if (rr <= mid) return query(L, l, mid, ll, rr);

	else if (ll > mid) return query(R, mid + 1, r, ll, rr);

	else return query(L, l, mid, ll, mid) | query(R, mid + 1, r, mid + 1, rr);

}

void modify(int x, int l, int r, int to)

{

	flag[x] = true;

	if (l == r) return;

	int mid = (l + r) >> 1, L = x << 1, R = L | 1;

	if (to <= mid) modify(L, l, mid, to);

	else modify(R, mid + 1, r, to);

}

bool Query(int x, int y)

{

	while (1)

	{

		if (top[x] == top[y])

		{

			if (deep[x] < deep[y]) return query(1, 1, cnt, dfsx[x], dfsx[y]);

			else return query(1, 1, cnt, dfsx[y], dfsx[x]);

		}

		if (deep[top[x]] > deep[top[y]])

			if (query(1, 1, cnt, dfsx[top[x]], dfsx[x])) return true;

			else x = fa[top[x]];

		else

		{

			if (query(1, 1, cnt, dfsx[top[y]], dfsx[y])) return true;

			else y = fa[top[y]];

		}

	}

}

void work(int x)

{

	for (int i = p[x]; i != -1; i = nxt[i])

		if (to[i] != fa[x])

			work(to[i]);

	for (int i = lr[x][0]; i <= lr[x][1]; i++)

		if (!Query(q[Q[i]][0], q[Q[i]][1]))

		{

			modify(1, 1, cnt, dfsx[x]);

			sta[++ans] = x;

			return;

		}

}

bool cmp(int x, int y) {return lca[x] < lca[y];}

int main()

{

	freopen("ping.in","r",stdin);

	freopen("ping.out","w",stdout);

	scanf("%d%d", &n, &m);

	for (int i = 0; i <= n; i++) p[i] = son[i] = -1, top[i] = size[i] = fa[i] = deep[i] = 0;

	for (int i = 1; i <= n * 4; i++) flag[i] = false;

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

	{

		scanf("%d%d", &u, &v);

		u--, v--;

		to[i * 2 - 1] = v;

		nxt[i * 2 - 1] = p[u];

		p[u] = i * 2 - 1;

		to[i * 2] = u;

		nxt[i * 2] = p[v];

		p[v] = i * 2;

	}

	deep[0] = 1;

	dfs(0);

	cnt = 0;

	dfs1(0);

	scanf("%d", &P);

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

	{

		scanf("%d%d", &u, &v);

		u--, v--;

		q[i][0] = u, q[i][1] = v;

		lca[i] = findlca(u, v);

		Q[i] = i;

	}

	sort(Q + 1, Q + P + 1, cmp);

	for (int i = 0; i <= n; i++) lr[i][0] = P + 1, lr[i][1] = 0;

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

	{

		lr[lca[Q[i]]][0] = min(lr[lca[Q[i]]][0], i);

		lr[lca[Q[i]]][1] = max(lr[lca[Q[i]]][1], i);

	}

	ans = 0;

	work(0);

	printf("%d\n", ans);

	for (int i = 1; i <= ans; i++) printf("%d ", sta[i] + 1);

	return 0;

}