#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<int> temp;
int res = INT_MAX;
int check(int h[][2])
{
int ht[100]={0};
int cnt = 0;
int n = temp.size();
for(int i=0; i<n; i++)
{
ht[h[i][0]] ++;
ht[h[i][1]] ++;
cnt += 2;
if(ht[h[i][0]] == 2) cnt -= 2;
else if(ht[h[i][0]] > 2) return 0;
if(ht[h[i][1]] == 2) cnt -= 2;
else if(ht[h[i][1]] > 2) return 0;
}
if(cnt == 2) return 1;
return 0;
}
void sub(int a[], int ind, int target, int n,int h[][2])
{
if(ind >= n) return;
if(target < 0) return;
if(target == 0)
{
if(check(h)){
int k = temp.size();
res = min(res, k);
}
return;
}
for(int i = ind; i<n; i++)
{
temp.push_back(i);
target -= a[i];
sub(a,i+1,target,n,h);
target += a[i];
temp.pop_back();
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
int u;
int u1,u2;
for(int i=0; i<N-2; i++)
{
for(int j=i+1; j<N-1; j++)
{
if(L[i] > L[j])
{
u = L[i];
L[i] = L[j];
L[j] = u;
u1 = H[i][0];
H[i][0] = H[j][0];
H[j][0] = u1;
u2 = H[i][1];
H[i][1] = H[j][1];
H[j][1] = u2;
}
}
}
sub(L,0,K,N-1,H);
if(res == INT_MAX) return -1;
return res;
}
