Untitled diff
11 removals
92 lines
13 additions
94 lines
// iostream is too mainstream
// iostream is too mainstream
#include <cstdio>
#include <cstdio>
// bitch please
// bitch please
#include <iostream>
#include <iostream>
#include <vector>
#include <vector>
#include <set>
#include <set>
#include <map>
#include <map>
#include <string>
#include <string>
#include <queue>
#include <queue>
#include <stack>
#include <stack>
#include <algorithm>
#include <algorithm>
#include <cmath>
#include <cmath>
#include <iomanip>
#include <iomanip>
#define dibs reserve
#define dibs reserve
#define OVER9000 1234567890123456780LL
#define OVER9000 1234567890123456780LL
#define patkan 9
#define patkan 9
#define tisic 47
#define tisic 47
#define soclose 1e-10
#define soclose 1e-10
#define pi 3.1415926535898
#define pi 3.1415926535898
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define chocolate win
#define chocolate win
#define ff first
#define ff first
#define ss second
#define ss second
#define abs(x) ((x < 0)?-(x):(x))
#define abs(x) ((x < 0)?-(x):(x))
#define uint unsigned int
#define uint unsigned int
#include <time.h>
#include <time.h>
// mylittlepony
// mylittlepony
using namespace std;
using namespace std;
vector< vector<int> > G;
vector< vector<int> > G;
vector<int> P;
vector<int> P;
vector<bool> vis;
vector<bool> vis;
vector<int> par;
vector<int> par;
vector<int> path;
vector<int> path;
void DFS(int R) {
void DFS(int R) {
vis[R] =true;
vis[R] =true;
ALL_THE(G[R],it) if(!vis[*it]) {
ALL_THE(G[R],it) if(!vis[*it]) {
// cesta R->*it
// cesta R->*it
P[*it] =1-P[*it];
P[*it] =1-P[*it];
path.push_back(*it);
path.push_back(*it);
par[*it] =R;
par[*it] =R;
DFS(*it);
DFS(*it);
// cesta *it->R
// cesta *it->R
path.push_back(R);
path.push_back(R);
P[R] =1-P[R];
P[R] =1-P[R];
// este raz?
// este raz?
if(P[*it] == 1) {
if(P[*it] == 1) {
// cesta R->*it->R
// cesta R->*it->R
path.push_back(*it);
path.push_back(*it);
path.push_back(R);
path.push_back(R);
P[*it] =0;
P[*it] =0;
P[R] =1-P[R];}
P[R] =1-P[R];}
}
}
}
}
int main() {
int main() {
cin.sync_with_stdio(0);
cin.sync_with_stdio(0);
cin.tie(0);
cin.tie(0);
int N,M;
int N,M;
cin >> N >> M;
cin >> N >> M;
G.resize(N);
G.resize(N);
for(int i =0; i < M; i++) {
for(int i =0; i < M; i++) {
int a,b;
int a,b;
cin >> a >> b;
cin >> a >> b;
G[--a].push_back(--b);
G[--a].push_back(--b);
G[b].push_back(a);}
G[b].push_back(a);}
P.resize(N);
P.resize(N);
for(int i =0; i < N; i++) cin >> P[i];
for(int i =0; i < N; i++) cin >> P[i];
vis.resize(N,false);
vis.resize(N,false);
par.resize(N);
par.resize(N);
path.push_back(0);
for(int i =0; i < N; i++) if(P[i] == 1) {
P[0] =1-P[0];
path.push_back(i);
DFS(0);
P[i] =0;
if(P[0] == 1 && !G[0].empty()) {
DFS(i);
path.push_back(G[0][0]);
if(P[i] == 1 && !G[i].empty()) {
P[G[0][0]] =1;
path.push_back(G[i][0]);
path.push_back(0);
P[G[i][0]] =1;
P[0] =0;
path.push_back(i);
path.push_back(G[0][0]);
P[i] =0;
P[G[0][0]] =0;}
path.push_back(G[i][0]);
P[G[i][0]] =0;}
break;}
for(int i =0; i < N; i++) if(P[i] == 1) {
for(int i =0; i < N; i++) if(P[i] == 1) {
cout << "-1\n";
cout << "-1\n";
return 0;}
return 0;}
cout << path.size() << "\n";
cout << path.size() << "\n";
for(uint i =0; i < path.size(); i++) cout << path[i]+1 << ((i+1 == path.size())?"\n":" ");
for(uint i =0; i < path.size(); i++) cout << path[i]+1 << ((i+1 == path.size())?"\n":" ");
return 0;}
return 0;}
// look at my code
// look at my code
// my code is amazing
// my code is amazing