/* 3 3 2 3 4 3 2 3 1 3 1 2 2 3 6 1 3 2 5 3 4 2 1 2 4 2 1 5 4 5 3 2 1 1 1 2 3 2 4 3 5 4 9 1 3 2 1 3 */ #include using namespace std; #define MAXN 1000010 #define MIN(a,b,c) min(a,min(b,c)) const long long INF = 1e9; int n, u, v; int len; int cost[4][MAXN], vis[MAXN], track[MAXN]; int dp[MAXN][4][4]; vector adj[MAXN], topo; class fastio { public: fastio() { ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); } } __fastio; void graph(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } void dfs(int v) { //Depth First Search vis[v] = 1; for(auto u : adj[v]) { if(!vis[u]) dfs(u); } //topological sorting topo.push_back(v); } int f(int i, int c, int p, int x) { if(i == n) return 0; if(dp[i][c][p] != -1) return dp[i][c][p]; track[x] = c; if(c == 1) { if(p == 2) return dp[i][c][p] = f(i+1,3,1,x+1) + cost[3][topo.at(i)]; if(p == 3) return dp[i][c][p] = f(i+1,2,1,x+1) + cost[2][topo.at(i)]; } if(c == 2) { if(p == 1) return dp[i][c][p] = f(i+1,3,2,x+1) + cost[3][topo.at(i)]; if(p == 3) return dp[i][c][p] = f(i+1,1,2,x+1) + cost[1][topo.at(i)]; } if(c == 3) { if(p == 1) return dp[i][c][p] = f(i+1,2,3,x+1) + cost[2][topo.at(i)]; if(p == 2) return dp[i][c][p] = f(i+1,1,3,x+1) + cost[1][topo.at(i)]; } } void solve() { cin >> n; //input - colors for(int i=1; i<=3; i++) { for(int j=1; j<=n; j++) cin >> cost[i][j]; } //forming adjaceny list for(int i=0; i> u >> v; graph(u,v); } //If there is a vertex with degree more than 2 then it is impossible to get distinct color for(int i=1; i<=n; i++) { if(adj[i].size() > 2) { puts("-1"); exit(0); } } //Finding the root node int root = -1; for(int i=1; i<=n; i++) { if(adj[i].size() == 1) { root = i; break; } } dfs(root); //getting the right order reverse(topo.begin(), topo.end()); //getting the answer memset(dp,-1,sizeof(dp)); int mini = INF; for(int i=1; i<=3; i++) { for(int j=1; j<=3; j++) { if(i != j) { mini = min(mini, f(0,i,j,0)); } } } cout << mini << endl; } int main() { __fastio; solve(); return 0; }