Domino massimale

Ho problemi su alcuni subtask che non mi spiego. Ho anche implementato due volte usando due approcci diversi ma faccio comunque solo 78 punti… Il problema sui subtask in questione (6, 9, 11, 15, 17) è che il programma restituisce la soluzione +1 (infatti se provo ad aumentare di 1 la soluzione finale fa bene solo quei subtask) e questo mi fa pensare che mi sfugge qualche caso particolare ma non arrivo a capire quale… qui codice:

#include <bits/stdc++.h>

int N, max = 1;
std::vector<std::pair<int, int> > tessere;
std::vector<bool> preso;

int solve(int s, int p);

int main(void) {
	std::ifstream in("input.txt");
	std::ofstream ou("output.txt");
	in >> N;
	int t1, t2;

	for(unsigned i = 0; i < N; ++i) {
		in >> t1 >> t2;
		tessere.push_back(std::make_pair(t1, t2));
		preso.push_back(false);
	}

	// per ogni possibile tessera iniziale
	for(int i = 0; i < tessere.size(); i++) {
		preso[i] = true;
		int gg = solve(i, 1);
		preso[i] = false;
	}

	ou << max;

	in.close();
	ou.close();
	return 0;
}

int solve(int s, int p) {
	// p rappresenta il numero di tessere che ho concatenato fin' ora
	if(p > max) max = p;
	for(int i = 0; i < N; i++) {
		// se non ho ancora preso quella tessera e quella tessara ha
		// almeno una faccia in comune con la precedente (s)
		if(!preso[i] && (tessere[s].first == tessere[i].first ||
				tessere[s].first == tessere[i].second ||
				tessere[s].second == tessere[i].first ||
				tessere[s].second == tessere[i].second)) {
			preso[i] = true;
			solve(i, p+1);
			preso[i] = false;
		}
	}
}

( http://pastebin.com/VRC8VTmr )

Quando fai il controllo per vedere se puoi concatenare i con s non tieni conto che solo una delle due facce di s può essere utilizzata.