#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector vi; typedef vector vvi; typedef pair pi; #define all(x) begin(x),end(x) #define rep(i,a,b) for(int i=a;i>& gr, int nedges, int src=0) { int n = sz(gr); vi D(n), its(n), eu(nedges),ret; vector s={{src,-1}}; // D[src]++; while(!s.empty()) { auto [x,eid] = s.back(); int y, e, &it = its[x], end = sz(gr[x]); if (it==end){ ret.push_back(eid); s.pop_back(); continue;} tie(y,e) = gr[x][it++]; if (!eu[e]) { D[x]--, D[y]++; eu[e]=1; s.push_back({y,e}); } } for (int x:D) if (x<0||sz(ret) != nedges+1) return {}; return {ret.rbegin(),ret.rend()}; } int main() { int n; cin >> n; string build; string prof; cin >> build; cin >> prof; int d2=0; int d3=0; // vi stopC; // vi sopM; vector edges = {{0,1},{1,0}}; vector ed = {-2,-2}; //edge's building rep(i,0,n) { char b=build[i]; char p=prof[i]; if (b==p) continue; if (b=='-') { // GEN if (p=='C') { edges.push_back({1,2}); ed.push_back(i); d2++; } else if (p=='M') { edges.push_back({1,3}); ed.push_back(i); d3++; } } else if (p=='-') { //STOP if (b=='C') { edges.push_back({2,1}); ed.push_back(i); d2--; // stopC.push_back(i); } else if (b=='M') { edges.push_back({3,1}); ed.push_back(i); d3--; // stopM.push_back(i); } } else { if (b=='C' && p=='M') { edges.push_back({2,3}); ed.push_back(i); d2--; d3++; } else if (b=='M' && p=='C') { edges.push_back({3,2}); ed.push_back(i); d3--; d2++; } } } rep(i,0,d2) { edges.push_back({2,1}); ed.push_back(-1); } rep(i,0,d3) { edges.push_back({3,1}); ed.push_back(-1); } vector> adj(4); rep(i,0,sz(edges)){ adj[edges[i].first].push_back({edges[i].second,i}); } vi path = eulerWalk(adj,sz(edges),0); path.erase(path.begin()); // for (auto p: edges) cout << "// " << p.first << ' ' << p.second << endl; int s=0; // cout << path.size() << '\n'; for(int i : path) { if (ed[i]<0) continue; // if (i==-2) continue; // (pick up prof for x) drive to building x (drop off prof for x) if (build[ed[i]] != '-') { s++; } s++; if (build[ed[i]] != '-') { s++; } } cout << s << '\n'; for(int i : path) { if (ed[i]<0) continue; // if (i==-2) continue; // (pick up prof for x) drive to building x (drop off prof for x) if (build[ed[i]] != '-') { cout << "PICKUP\n"; } cout << "DRIVE " << ed[i]+1 << "\n"; if (build[ed[i]] != '-') { cout << "DROPOFF\n"; } } } // 3 // CM- // -CM // 0 1 // 1 0 // 2 1 // 1 3 // 3 1 /* 3 CM- -CM // 0 1 // 1 0 // 2 1 // 3 2 // 1 3 PICKUP DRIVE 1 DROPOFF PICKUP DRIVE 68 DROPOFF DRIVE 46 PICKUP DRIVE 78 DROPOFF PICKUP DRIVE 68 DROPOFF */ /* 1 C C // 0 1 // 1 0 PICKUP DRIVE 1CM- -CM // 0 1 // 1 0 // 2 1 // 3 2 // 1 3 PICKUP DRIVE -1 DROPOFF PICKUP DRIVE 1 DROPOFF DRIVE 3 PICKUP DRIVE 2 DROPOFF PICKUP DRIVE 1 DROPOFF DROPOFF PICKUP DRIVE 68 DROPOFF */ /* CM- -CM // 0 1 // 1 0 // 2 1 // 3 2 // 1 3 PICKUP DRIVE -1 DROPOFF PICKUP DRIVE 1 DROPOFF DRIVE 3 PICKUP DRIVE 2 DROPOFF PICKUP DRIVE 1 DROPOFF */