#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class PieOrDolphin { public:
vector <int> Distribute(vector <int> choice1, vector <int> choice2)
{
const int E = choice1.size();
typedef int EdgeID, Vert;
vector< map<EdgeID,Vert> > G(50);
for(int i=0; i<E; ++i) {
int v = choice1[i];
int u = choice2[i];
G[v][i] = u;
G[u][i] = v;
}
vector<int> ans(E);
function<void(int)> remove_cycle = [&](int S)
{
function<bool(int)> dfs;
vector<bool> used(E);
stack<pair<EdgeID,int>> stk;
dfs = [&](int v) {
for(auto eu: G[v]) {
EdgeID e = eu.first;
Vert u = eu.second;
if(used[e])
continue;
used[e] = true;
stk.emplace(e, choice1[e]==v ? 1 : 2);
if(u == S) {
// found
while(!stk.empty()) {
EdgeID ee = stk.top().first;
int dir = stk.top().second;
stk.pop();
ans[ee] = dir;
for(int v=0; v<50; ++v)
G[v].erase(ee);
}
return true;
} else {
if(dfs(u))
return true;
stk.pop();
}
}
return false;
};
while(dfs(S)) {}
};
function<void(Vert)> remove_tree = [&](int S)
{
function<void(Vert,Vert,int)> rec;
rec = [&](int v, int p, int d) {
int size = G[v].size() - 1;
int cnt = 0;
int lim = (d==+1 ? size/2 : (size+1)/2);
for(auto& eu: G[v])
{
EdgeID e = eu.first;
Vert u = eu.second;
if(u==p)
continue;
if(cnt++ < lim)
{
ans[e] = choice1[e]==v ? 1 : 2;
rec(u, v, -1);
}
else
{
ans[e] = choice1[e]==v ? 2 : 1;
rec(u, v, +1);
}
}
G[v].clear();
};
rec(S, -1, -1);
};
for(int v=0; v<50; ++v)
remove_cycle(v);
for(int v=0; v<50; ++v)
if(!G[v].empty())
remove_tree(v);
return ans;
}
};
// BEGIN CUT HERE
int score(vector <int> choice1, vector <int> choice2, vector<int> ans) {
vector<int> s(50);
for(int i=0; i<choice1.size(); ++i) {
int u = choice1[i];
int v = choice2[i];
if(ans[i]==1) {
s[u]++;
s[v]--;
} else {
assert(ans[i]==2);
s[u]--;
s[v]++;
}
}
int total = 0;
for(int si : s) total += abs(si);
return total;
}
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(int Expected, int Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(score(choice1,choice2,_), score(choice1,choice2,PieOrDolphin().Distribute(choice1, choice2)));}
int main(){
CASE(0)
int choice1_[] = {10, 20, 10};
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = {20, 30, 20};
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = {2, 2, 1 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(1)
int choice1_[] = {0, 0};
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = {1, 1};
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = {2, 1 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(2)
int choice1_[] = {0, 1, 2, 3, 5, 6, 7, 8};
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = {8, 7, 6, 5, 3, 2, 1, 0};
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = {2, 2, 2, 2, 2, 2, 2, 2 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(3)
int choice1_[] = {49, 0, 48, 1};
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = {3, 4, 5, 6};
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = {2, 2, 2, 2 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(4)
int choice1_[] = {21,4,14,0,31,46,1,34,2,3,27,19,47,46,17,11,41,12,31,0,34,18,8,14,23,40,0,18,48,35,42,24,25,32,25,44,17,6,44,34,12,39,43,39,26,
34,10,6,13,2,40,15,16,32,32,29,1,23,8,10,49,22,10,15,40,20,0,30,1,43,33,42,28,39,28,4,38,11,5,1,47,12,0,22,20,33,33,34,18,8,23,6};
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = {25,5,39,20,44,47,11,49,42,17,25,15,23,11,32,17,24,4,11,47,27,41,40,0,49,27,5,28,6,11,18,0,17,1,0,32,45,28,17,5,13,40,40,25,33,
7,8,32,12,0,39,30,8,39,23,9,8,34,34,37,5,1,24,23,0,29,11,42,29,40,24,18,37,1,21,0,31,47,23,33,45,48,31,11,40,45,24,22,19,26,37,39};
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = {2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 1 };
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
/*
CASE(5)
int choice1_[] = ;
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = ;
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = ;
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
CASE(6)
int choice1_[] = ;
vector <int> choice1(choice1_, choice1_+sizeof(choice1_)/sizeof(*choice1_));
int choice2_[] = ;
vector <int> choice2(choice2_, choice2_+sizeof(choice2_)/sizeof(*choice2_));
int __[] = ;
vector <int> _(__, __+sizeof(__)/sizeof(*__));
END
*/
}
// END CUT HERE