Pagini recente » Cod sursa (job #1010037) | Cod sursa (job #2272565) | Cod sursa (job #1024524) | Cod sursa (job #2825866) | Cod sursa (job #214830)
Cod sursa(job #214830)
#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 1024
#define KMAX 4020
#define pb push_back
#define sz size()
int N, M, K;
vector<int> G[2*NMAX];
vector<int> sol;
int ST[2*NMAX];
int X[KMAX], Y[KMAX];
int SW[NMAX][NMAX], IND[NMAX][NMAX];
int BF(int nod)
{
int viz[NMAX];
int cd[NMAX];
int TT[NMAX];
int i, j, x, y;
memset(viz, 0, sizeof(viz));
viz[nod] = 1;
cd[0] = 1;
cd[1] = nod;
for (i = 1; i <= cd[0]; i++)
for (j = 0; j < G[ cd[i] ].sz; j++)
if (!viz[ G[ cd[i] ][j] ])
{
cd[ ++cd[0] ] = G[ cd[i] ][j];
viz[ G[ cd[i] ][j] ] = 1;
TT[ G[ cd[i] ][j] ] = cd[i];
}
for (i = 1; i < N+M; i++)
if (i != nod && ST[i] && viz[i])
{
j = i;
while (j != nod)
{
x = j;
y = TT[j];
if (x >= N) SW[y][x-N+1]=!SW[y][x-N+1];
else SW[x][y-N+1]=!SW[x][y-N+1];
j=TT[j];
}
ST[nod]=0;
ST[i]=0;
return 1;
}
return 0;
}
void solve()
{
int i, j, x, y;
scanf("%d %d %d", &N, &M, &K);
for (i = 1; i < N; i++)
{
scanf("%d ", &x);
ST[i] = x;
}
for (i = 1; i < N; i++)
{
scanf("%d ", &x);
ST[i] = (ST[i]^x);
}
for (i = 0; i < M-1; i++)
{
scanf("%d ", &x);
ST[ N+i ] = x;
}
for (i = 0; i < M-1; i++)
{
scanf("%d ", &x);
ST[ N+i ] = (ST[ N+i ]^x);
}
for (i = 0; i < K; i++)
scanf("%d ", &X[i]);
for (i = 0; i < K; i++)
scanf("%d ", &Y[i]);
for (i = 0; i < K; i++)
{
G[ X[i] ].pb(N+Y[i]-1);
G[ N+Y[i]-1 ].pb(X[i]);
IND[ X[i] ][ Y[i] ] = i;
}
// for (i = 1; i < N+M; i++)
// printf("%d ",ST[i]);
int ok=1;
for (i = 1; i < N+M; i++)
if (ST[i])
{
ok=BF(i);
if (!ok)
{
printf("-1\n");
return;
}
}
for (i = 1; i <= N; i++)
for (j = 1; j <= M; j++)
if (SW[i][j]) sol.pb(IND[i][j]);
printf("%d ",sol.sz);
for (i = 0; i < sol.sz; i++)
printf("%d ", sol[i]);
printf("\n");
}
int main()
{
freopen("switch.in", "r", stdin);
freopen("switch.out", "w", stdout);
int T;
for (scanf("%d ", &T); T; T--)
{
solve();
for (int i = 1; i <= N+M; i++)
G[i].clear();
memset(SW, 0, sizeof(SW) );
sol.clear();
}
return 0;
}