SPOJ.com - Problem ADAPARTI

Here’s the Prombem : https://www.spoj.com/problems/ADAPARTI/35
I wonder if there’s a solution which time complexity than O(T * n * 3 ^ 12) ? Isn’t the time limit too strict for this problem?
Here’s my current solution with TLE : https://ideone.com/W1eNGt11
The core of the algorithm is that no exactly two edges can be connected between any three points.