#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;
static const int INF = 0x7fffffff;
template<typename T=LL>
struct FenwickTree
{
vector<T> x;
FenwickTree(size_t n) : x(n) {}
void incr( int k, const T& a ) { // z[k] += a;
for(; k < x.size(); k|=k+1)
x[k] += a;
}
T sum(int i, int j) { // Sigma z[i,j) excl.
return sum_impl(j-1) - sum_impl(i-1);
}
T sum_impl(int j) { // Sigma z[0,j] incl.
T v = T();
for(; j>=0; j=(j&(j+1))-1)
v += x[j];
return v;
}
};
class GraphInversions { public:
int getMinimumInversions(vector <int> A, vector <int> B, vector <int> V, int K)
{
int N = A.size();
vector<vector<int>> G(N);
for(int i=0; i<N; ++i) {
int a=A[i], b=B[i];
G[a].push_back(b);
G[b].push_back(a);
}
int best = INF;
for(int s=0; s<N; ++s)
best = min(best, solveRooted(K, s, N, G, V));
return (best==INF ? -1 : best);
}
int solveRooted(size_t K, int S, int N, const vector<vector<int>>& G, const vector<int>& V)
{
int best = INF;
vector<bool> vis(N, false);
FenwickTree<int> fw(1001);
vector<int> score_stack;
function<void(int)> rec;
rec = [&](int v) {
int s = (score_stack.empty() ? 0 : score_stack.back());
s += fw.sum(V[v]+1, 1001);
fw.incr(V[v], 1);
score_stack.push_back(s);
if(score_stack.size() == K) {
best = min(best, score_stack.back());
fw.incr(V[v], -1);
score_stack.pop_back();
return;
}
vis[v] = true;
for(int u: G[v]) if(!vis[u])
rec(u);
vis[v] = false;
fw.incr(V[v], -1);
score_stack.pop_back();
};
rec(S);
return best;
}
};
// 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 int& Expected, const 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(_, GraphInversions().getMinimumInversions(A, B, V, K));}
int main(){
CASE(0)
int A_[] = {0,1,2};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,0};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {40,50,60};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 3;
int _ = 0;
END
CASE(1)
int A_[] = {0,1,2,3};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3,0};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {60,40,50,30};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 3;
int _ = 1;
END
CASE(2)
int A_[] = {0,1,2,3,0};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3,0,4};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {10,10,10,5,5};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 5;
int _ = 1;
END
CASE(3)
int A_[] = {0,1,2,3,0,2};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {1,2,3,0,4,5};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {10,2,5,3,7,1};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 6;
int _ = -1;
END
CASE(4)
int A_[] = {5,7,7,5,5,7,6,4};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,0,2,0,1,4,7,3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {15,10,5,30,22,10,5,2};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 6;
int _ = 3;
END
CASE(4)
int A_[] = {5,7,7,5,5,7,6,4};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,0,2,0,1,4,7,3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {15,10,5,30,22,10,5,2};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 1;
int _ = 0;
END
CASE(4)
int A_[] = {5,7,7,5,5,7,6,4};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2,0,2,0,1,4,7,3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {15,10,5,30,22,10,5,2};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 2;
int _ = 0;
END
CASE(5)
int A_[] = {0,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,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {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,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,0, 0};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = {137,1000,88,120,582,208,9,350,562,432,981,242,183,459,223,900,186,388,530,952,89,556,868,927,277,912,28,218,835,68,142,489,503,729,238,140,86,155,231,326,989,515,276,187,849,436,548,234,591,57,485,222,924,307,214,528,748,32,817,636,623,479,241,594,715,830,663,739,749,175,889,397,812,466,393,458,866,410,145,317,158,294,511,232,629,118,413,134,875,827,713,942,374,5,25,159,796,37,272,373,957,536,686,762,514,4,150,422,360,494,700,21,525,173,496,92,320,551,412,885,516,36,213,712,44,362,872,23,492,98,77,895,970,292,632,474,226,504,245,152,780,574,626,842,335,247,70,668,707,240,587,611,386,377,461,324,347,547,714,168,55,163,847,851,971,475,549,196,445,726,338,993,608,117,64,406,291,794,974,544,311,604,392,255,356,571,125,104,473,945,829,51,967,176,270,220,249,361,941,681,999,1000,400,658,178,79,275,627,27,677,217,287,982,246,581,280,63,441,184,826,1,201,598,266,435,289,710,421,926,308,965,462,693,674,887,566,876,949,84,731,946,532,96,293,622,521,405,283,928,824,848,793,185,709,428,288,682,304,33,983,382,807,20,327,771,526,107,29,41,61,589,439,774,207,313,938,584,734,575,603,934,278,894,832,583,790,651,735,13,998,899,181,675,169,228,954,524,453,344,988,256,612,881,480,251,416,447,861,891,342,724,69,379,58,787,755,490,914,764,250,100,366,538,133,45,923,925,661,833,404,139,570,878,153,476,640,510,94,102,992,991,588,808,215,6,329,630,420,138,922,325,741,281,654,235,157,786,221,585,761,684,920,939,509,740,389,593,339,606,778,976,264,643,53,834,452,959,273,552,862,483,110,358,518,561,752,792,619,905,631,437,417,50,760,953,290,703,229,99,670,837,702,396,573,470,194,933,664,968,108,803,427,719,537,759,555,381,372,706,672,52,691,917,180,602,932,442,701,224,904,814,628,545,192,72,501,454,297,24,472,285,642,305,770,506,90,364,296,864,73,973,543,368,767,669,690,121,892,298,550,35,87,76,115,825,558,996,143,888,346,129,782,844,870,144,721,613,261,216,75,502,414,487,415,805,777,898,295,401,860,22,321,219,692,783,191,482,529,678,340,541,666,802,995,49,695,597,797,237,434,10,937,964,921,747,638,233,349,577,823,328,947,132,122,963,56,399,863,500,901,425,478,135,310,127,230,659,595,711,341,65,810,789,652,936,568,839,345,689,67,111,212,154,580,854,16,34,151,633,54,517,443,80,209,30,609,621,314,306,610,248,337,596,732,378,756,979,426,172,858,18,813,493,383,685,519,791,601,836,704,2,856,31,534,271,486,81,497,353,463,334,174,166,19,554,471,542,614,114,688,97,488,648,411,244,535,975,728,553,109,82,673,977,316,394,897,407,267,935,484,206,637,641,818,644,333,958,831,39,161,444,720,656,170,969,811,438,204,91,365,819,838,708,911,910,419,846,456,505,758,879,662,744,865,929,768,564,639,653,750,309,586,855,60,705,576,873,160,269,804,569,997,730,351,200,395,972,431,599,560,165,7,164,210,252,650,660,776,448,916,391,559,867,520,357,303,171,418,123,74,687,539,179,944,716,375,119,12,676,785,130,913,930,424,799,620,429,877,101,980,987,15,274,477,754,572,850,763,149,908,769,753,369,315,840,821,880,14,883,635,370,655,513,940,343,788,253,148,457,330,195,961,918,962,262,348,667,199,254,46,605,822,498,727,845,906,182,617,47,286,284,318,696,557,646,376,112,239,956,806,430,423,455,189,380,355,645,624,546,95,909,853,984,717,757,579,540,105,902,615,859,893,698,948,211,227,512,449,371,481,828,93,450,17,886,745,156,300,177,775,131,994,563,190,943,857,843,440,3,665,259,795,11,83,126,202,282,465,634,578,66,103,38,841,398,903,680,592,600,966,820,468,198,40,869,124,671,197,162,319,302,567,403,128,147,363,737,884,896,907,48,116,616,71,390,257,523,990,408,527,260,385,657,331,809,590,736,402,522,193,533,683,499,694,746,188,265,931,106,773,738,919,955,205,647,742,141,951,352,78,798,816,59,607,62,203,915,950,301,978,469,146,531,874,43,495,387,508,751,359,722,882,890,113,263,772,718,42,781,384,167,766,312,26,679,725,765,225,85,268,433,460,446,332,733,279,243,985,852,258,565,464,507,986,236,354,367,625,697,136,336,723,743,322,871,491,784,618,800,299,699,323,8,779,409,467,451,649,1000,1000};
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = 1000;
int _ = -1;
END
/*
CASE(6)
int A_[] = ;
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = ;
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int V_[] = ;
vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
int K = ;
int _ = ;
END
*/
}
// END CUT HERE