#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>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;
class CentaurCompany { public:
struct State {
int nNode;
vector< vector< vector<double> > > th; // nHumanNodes -> nEq -> nEq -> prob
vector< vector< vector<double> > > tk; // nHumanNodes -> nEq -> nEq -> prob
};
double getvalue(vector <int> a, vector <int> b)
{
int N = a.size() + 1;
vector< vector<int> > G(N);
for(int i=0; i<a.size(); ++i) {
G[a[i]-1].push_back(b[i]-1);
G[b[i]-1].push_back(a[i]-1);
}
double e = 0.0;
State s = rec(-1, 0, G);
for(int ah=0; ah<=s.nNode; ++ah)
for(int ahe=0; ahe<=ah; ++ahe)
for(int ake=0; ake<=(s.nNode-ah); ++ake)
{
int ak = s.nNode - ah;
{
double p = s.th[ah][ahe][ake];
e += p * (max(2*(ahe-1)-ah,0)+max(2*(ake-1)-ak,0));
}
{
double p = s.tk[ah][ahe][ake];
e += p * (max(2*(ahe-1)-ah,0)+max(2*(ake-1)-ak,0));
}
}
return e;
}
State rec(int p, int v, const vector<vector<int> >& G)
{
State s = {1,
vector< vector< vector<double> > >(2, vector< vector<double> >(2, vector<double>(2))),
vector< vector< vector<double> > >(2, vector< vector<double> >(2, vector<double>(2)))
};
s.th[1][1][0] = 0.5;
s.tk[0][0][1] = 0.5;
for(int i=0; i<G[v].size(); ++i) if(G[v][i] != p)
s = combine(s, rec(v, G[v][i], G));
return s;
}
State combine(const State& a, const State& b)
{
int N = a.nNode + b.nNode;
State s = {N,
vector< vector< vector<double> > >(N+1, vector< vector<double> >(N+1, vector<double>(N+1))),
vector< vector< vector<double> > >(N+1, vector< vector<double> >(N+1, vector<double>(N+1)))
};
for(int ah=0; ah<=a.nNode; ++ah)
for(int ahe=0; ahe<=ah; ++ahe)
for(int ake=0; ake<=(a.nNode-ah); ++ake)
for(int bh=0; bh<=b.nNode; ++bh)
for(int bhe=0; bhe<=bh; ++bhe)
for(int bke=0; bke<=(b.nNode-bh); ++bke) {
if(ahe+bhe!=0)
s.th[ah+bh][ahe+bhe-1][ake+bke] += a.th[ah][ahe][ake]*b.th[bh][bhe][bke];
s.th[ah+bh][ahe+bhe][ake+bke] += a.th[ah][ahe][ake]*b.tk[bh][bhe][bke];
s.tk[ah+bh][ahe+bhe][ake+bke] += a.tk[ah][ahe][ake]*b.th[bh][bhe][bke];
if(ake+bke!=0)
s.tk[ah+bh][ahe+bhe][ake+bke-1] += a.tk[ah][ahe][ake]*b.tk[bh][bhe][bke];
}
return s;
}
};
// BEGIN CUT HERE
#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(const double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
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(_, CentaurCompany().getvalue(a, b));}
int main(){
CASE(0)
int a_[] = {1};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {2};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = 0.0;
END
CASE(1)
int a_[] = {1,1,1};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {2,3,4};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = 0.125;
END
CASE(2)
int a_[] = {1,2,3,2,2};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {2,3,4,5,6};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = 0.375;
END
CASE(3)
int a_[] = {1,2,3,4,5,6,7,8,9};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {2,3,4,5,6,7,8,9,10};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = 0.41796875;
END
CASE(4)
int a_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = 15.500000001076842;
END
CASE(5)
int a_[] = {10, 7, 2, 5, 6, 2, 4, 9, 7};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {8, 10, 10, 4, 1, 6, 2, 2, 3};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = 0.646484375;
END
CASE(6)
int a_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = -1;
END
/*
CASE(7)
int a_[] = ;
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = ;
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
double _ = ;
END
*/
}
// END CUT HERE