// #includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; // }}} // pre-written code {{{ #define REP(i,n) for(int i=0;i<(int)(n);++i) #define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i) #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i) #define LET(x,a) __typeof(a) x(a) //#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i) #define ALL(c) (c).begin(), (c).end() #define MP make_pair #define EXIST(e,s) ((s).find(e)!=(s).end()) #define RESET(a) memset((a),0,sizeof(a)) #define SET(a) memset((a),-1,sizeof(a)) #define PB push_back #define DEC(it,command) __typeof(command) it=command //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl; const int INF=0x3f3f3f3f; typedef long long Int; typedef unsigned long long uInt; #ifdef __MINGW32__ typedef double rn; #else typedef long double rn; #endif typedef pair pii; /* #ifdef MYDEBUG #include"debug.h" #include"print.h" #endif */ // }}} int vis[1001000]; //{{{ Graph typedef int Weight; struct Edge { int src, dst, rev; Weight weight; Edge(int src, int dst, Weight weight=1,int rev=-1) : src(src), dst(dst), weight(weight), rev(rev) { } }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector Edges; typedef vector Graph; typedef vector Array; typedef vector Matrix; //add bi-directional edge void addBiEdge(Graph &g,int from ,int to, Weight w=1){ while(g.size()dst,b); } } int A,B,C,D; bool check(int N,const vector &e){ g.assign(N,Edges()); REP(i,e.size())g[e[i].first].push_back(Edge(e[i].first,e[i].second)); set s; REP(i,e.size()){ assert(e[i].first!=e[i].second); assert(0<=e[i].first and e[i].first a,b,c; cin>>A>>B>>C>>D; if(A==C and B==C){ if(A==1 or D e; REP(i,a.size()){ if(i+10 and c.size()>0)e.push_back(make_pair(a.back(),c.front())); if(b.size()>0 and c.size()>0)e.push_back(make_pair(b.back(),c.front())); REP(i,c.size()){ if(i+1