To solve this problem, we will first note that the stickman has a central edge, i.e. the torso, to which every other edge is connected, and unlike the arms and legs there is no ambiguity about which edge has been used for which torso as there is only one torso.

So if we iterate over every edge of the given graph and count how many times we can use the given edge as a torso and add all those values up, we will get our answer. So lets consider some edge uv (between th vertices u and v), and try and find out how many stickmen can be made with uv as a torso.

The first instinct is to pick some 3 neighbors of u and some 2 neighbors of v. So we multiply the number of ways we can pick 3 neighbors of u with the number of ways we can pick 2 neighbors of v and would add that to our answer. However, that is wrong as there may be some vertices which are neighbors of both u and v and we may end up picking the same vertex twice in one stickman, once as an arm or a head, and once as a leg.

Clearly our previous approach does some overcounting so lets fix that. When we are processing edge uv we will divide the neighbors of u and v into 3 categories:

1) Adjacent to both u and v.

2) Adjacent to just u.

3) Adjacent to just v.

Now, when we are counting number of ways to pick 3 neighbors of u, we will consider the following cases: All of them are from category 2, 2 of them are from category 2 and 1 of them is from category 1, 1 of them is category 2 and 2 are from category 2 and finally when all of them are from category 1. Similarly, we have multiple cases for the 2 neighbors of v we will pick. We will consider all possible pairs of these cases and add the answer for each to our final answer.

The only detail that is left is how to find out the number of ways to pick r vertices from a set of n vertices. This is a fairly common result in combinatorics and is given by: n!/(r! (n-r)!) Refer here for more details : https://en.wikipedia.org/wiki/Combination

// Errichto
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const ll INF = (ll) inf * inf;

struct coin {
	int value, weight, id;
	bool operator < (coin b) const {
		return value < b.value;
	}
};
struct info {
	ll minStart = 0, sumValue = 0, sumWeight = 0;
	int mask = 0;
	ll minMatchingLeft(int goal) {
		return max(minStart, goal - sumValue);
	}
};

info process(vector<coin> subset) {
	// "subset" is sorted by value
	info x;
	for(coin c : subset) {
		x.minStart = max(x.minStart, c.value - x.sumValue - 1);
		x.sumValue += c.value;
		x.sumWeight += c.weight;
	}
	return x;
}

void prepare(vector<coin> w, vector<info> & impo, bool isFirstHalf) {
	int n = w.size();
	REP(mask, 1 << n) {
		vector<coin> subset;
		REP(i, n) if(mask & (1 << i)) subset.pb(w[i]);
		info x = process(subset);
		x.mask = mask;
		if(x.minStart == 0 || !isFirstHalf)
			impo.pb(x);
	}
}

int main() {
	int n, goal;
	scanf("%d%d", &n, &goal);
	vector<coin> all;
	RI(i, n) {
		coin c;
		c.id = i;
		scanf("%d%d", &c.value, &c.weight);
		all.pb(c);
	}
	sort(all.begin(), all.end());
	vector<coin> small, big;
	REP(i, n) {
		if(i < n / 2) small.pb(all[i]);
		else big.pb(all[i]);
	}
	vector<info> left, right;
	prepare(small, left, true);
	prepare(big, right, false);
	sort(left.begin(), left.end(), [](info a, info b)
		{return a.sumValue > b.sumValue;});
	sort(right.begin(), right.end(), [goal](info a, info b)
		{return a.minMatchingLeft(goal) > b.minMatchingLeft(goal);});
	int iL = 0;
	pair<ll,int> bestLeft = mp(INF, -1);
	pair<ll, pair<int,int> > ans = mp(INF, mp(-1, -1));
	for(info r : right) {
		//printf("%lld %lld\n", left[iL].sumValue, r.minMatchingLeft(goal));
		while(iL < (int) left.size() && left[iL].sumValue >= r.minMatchingLeft(goal)) {
			bestLeft = min(bestLeft, mp(left[iL].sumWeight, left[iL].mask));
			++iL;
		}
		ans = min(ans, mp(r.sumWeight + bestLeft.st, mp(bestLeft.nd, r.mask)));
		//printf("%lld+%lld\n", r.sumWeight, bestLeft.st);
	}
	if(ans.st >= INF) puts("-1");
	else {
		vi w;
		REP(i, (int) small.size())
			if(ans.nd.st & (1 << i))
				w.pb(small[i].id);
		REP(i, (int) big.size())
			if(ans.nd.nd & (1 << i))
				w.pb(big[i].id);
		printf("%d\n", (int) w.size());
		for(int a : w) printf("%d ", a);
		puts("");
	}
	return 0;
}

// Errichto
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const ll INF = (ll) inf * inf;

struct coin {
	int value, weight, id;
	bool operator < (coin b) const {
		return value < b.value;
	}
};
struct info {
	ll minStart = 0, sumValue = 0, sumWeight = 0;
	int mask = 0;
	ll minMatchingLeft(int goal) {
		return max(minStart, goal - sumValue);
	}
};

void rec(int i, vector<coin> & w, vector<info> & impo, info & x, bool isFirstHalf) {
	if(i == (int) w.size()) {
		if(x.minStart == 0 || !isFirstHalf)
			impo.pb(x);
		return;
	}
	rec(i + 1, w, impo, x, isFirstHalf);
	info memo = x;
	x.minStart = max(x.minStart, w[i].value - x.sumValue - 1);
	x.sumValue += w[i].value;
	x.sumWeight += w[i].weight;
	x.mask += 1 << i;
	rec(i + 1, w, impo, x, isFirstHalf);
	x = memo;
}

void prepare(vector<coin> w, vector<info> & impo, bool isFirstHalf) {
	info x;
	rec(0, w, impo, x, isFirstHalf);
}

int main() {
	int n, goal;
	scanf("%d%d", &n, &goal);
	vector<coin> all;
	RI(i, n) {
		coin c;
		c.id = i;
		scanf("%d%d", &c.value, &c.weight);
		all.pb(c);
	}
	sort(all.begin(), all.end());
	vector<coin> small, big;
	REP(i, n) {
		if(i < n / 2) small.pb(all[i]);
		else big.pb(all[i]);
	}
	vector<info> left, right;
	prepare(small, left, true);
	prepare(big, right, false);
	sort(left.begin(), left.end(), [](info a, info b)
		{return a.sumValue > b.sumValue;});
	sort(right.begin(), right.end(), [goal](info a, info b)
		{return a.minMatchingLeft(goal) > b.minMatchingLeft(goal);});
	int iL = 0;
	pair<ll,int> bestLeft = mp(INF, -1);
	pair<ll, pair<int,int> > ans = mp(INF, mp(-1, -1));
	for(info r : right) {
		while(iL < (int) left.size() && left[iL].sumValue >= r.minMatchingLeft(goal)) {
			bestLeft = min(bestLeft, mp(left[iL].sumWeight, left[iL].mask));
			++iL;
		}
		ans = min(ans, mp(r.sumWeight + bestLeft.st, mp(bestLeft.nd, r.mask)));
	}
	if(ans.st >= INF) puts("-1");
	else {
		vi w;
		REP(i, (int) small.size())
			if(ans.nd.st & (1 << i))
				w.pb(small[i].id);
		REP(i, (int) big.size())
			if(ans.nd.nd & (1 << i))
				w.pb(big[i].id);
		printf("%d\n", (int) w.size());
		for(int a : w) printf("%d ", a);
		puts("");
	}
	return 0;
}

From a number 'x' greater than 2 you can't go to any numbers other than 2, x-2 and x+2 (proof: the distance to other numbers is even, so it can't be prime). From this fact you can prove that any optimal path between some 'a' and 'b' uses only vertices 2, a-2, a, a+2, b-2, b, b+2. If you want to prove it, use the fact that after moving to some number other than those seven, we will shortly have to get back to a number 2. It's important here that (except for a triple 3, 5, 7) the three consecutive odd numbers numbers y, y+2, y+4 can't be all primes.

For each of those seven numbers you must check if it's prime and for each pair you must check if its difference is prime. Then you should run BFS. It can be proved that there exists at most one optimal way so the answer "Poor Benny" never happens, but it doesn't affect the implementation much.