Untitled diff
3 removals
97 lines
28 additions
121 lines
#include <cstdio>
#include <cstdio>
#include <cstdlib>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <algorithm>
#include <algorithm>
#include <utility>
#include <utility>
#include <string>
#include <string>
#include <iostream>
#include <iostream>
#include <cmath>
#include <cmath>
#define MAXN 400005
#define MAXN 400005
using namespace std;
using namespace std;
struct datanode
struct datanode
{
{
int a, b;
int a, b;
};
};
static int s[MAXN];
static int s[MAXN];
static int a[MAXN];
static int a[MAXN];
static int p[MAXN];
static int p[MAXN];
static char b[MAXN];
static char b[MAXN];
static int res[MAXN];
static int res[MAXN];
int resc;
int resc;
void DFS (int point, int par)
void DFS (int point, int par)
{
{
res[resc] = point;
res[resc] = point;
resc++;
resc++;
p[point] ^= 1;
p[point] ^= 1;
int i;
int i;
for (i = s[point]; i < s[point+1]; i++)
for (i = s[point]; i < s[point+1]; i++)
{
{
if (!b[a[i]])
if (!b[a[i]])
{
{
b[a[i]] = 1;
b[a[i]] = 1;
DFS(a[i], point);
DFS(a[i], point);
}
}
}
}
if (par == -1)
if (par == -1)
{
{
if (p[point]) resc--;
if (p[point])
{
resc--;
p[point] ^= 1;
}
return;
return;
}
}
if (p[point])
if (p[point])
{
{
res[resc] = par;
res[resc] = par;
resc++;
resc++;
p[par] ^= 1;
p[par] ^= 1;
res[resc] = point;
res[resc] = point;
resc++;
resc++;
p[point] ^= 1;
p[point] ^= 1;
}
}
res[resc] = par;
res[resc] = par;
resc++;
resc++;
p[par] ^= 1;
p[par] ^= 1;
}
}
int main ()
int main ()
{
{
int N, M;
int N, M;
scanf("%d %d",&N,&M);
scanf("%d %d",&N,&M);
static struct datanode data[MAXN];
static struct datanode data[MAXN];
memset(s,0,sizeof(s));
memset(s,0,sizeof(s));
int i;
int i;
for (i = 0; i < M; i++)
for (i = 0; i < M; i++)
{
{
scanf("%d %d",&(data[i].a),&(data[i].b));
scanf("%d %d",&(data[i].a),&(data[i].b));
(data[i].a)--;
(data[i].a)--;
(data[i].b)--;
(data[i].b)--;
s[data[i].a]++;
s[data[i].a]++;
s[data[i].b]++;
s[data[i].b]++;
}
}
for (i = 1; i <= N; i++) s[i] += s[i-1];
for (i = 1; i <= N; i++) s[i] += s[i-1];
for (i = 0; i < M; i++)
for (i = 0; i < M; i++)
{
{
s[data[i].a]--;
s[data[i].a]--;
a[s[data[i].a]] = data[i].b;
a[s[data[i].a]] = data[i].b;
s[data[i].b]--;
s[data[i].b]--;
a[s[data[i].b]] = data[i].a;
a[s[data[i].b]] = data[i].a;
}
}
memset(b,0,sizeof(b));
memset(b,0,sizeof(b));
for (i = 0; i < N; i++) scanf("%d",&(p[i]));
for (i = 0; i < N; i++) scanf("%d",&(p[i]));
resc = 0;
resc = 0;
b[0] = 1;
DFS(0, -1);
int point = 0;
while ((point < N) && (!p[point])) point++;
if (point == N)
{
printf("0\n");
return 0;
}
b[point] = 1;
DFS(point, -1);
for (i = 0; i < N; i++)
{
if (p[i])
{
printf("-1\n");
return 0;
}
}
printf("%d\n",resc);
printf("%d\n",resc);
if (resc)
if (resc)
{
{
for (i = 0; i < resc; i++)
for (i = 0; i < resc; i++)
{
{
if (i) printf(" ");
if (i) printf(" ");
printf("%d",res[i] + 1);
printf("%d",res[i] + 1);
}
}
printf("\n");
printf("\n");
}
}
return 0;
return 0;
}
}