# USACO : Wormholes

```
/*
PROG: wormhole
LANG: C++
*/

#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
#define MAX_N 12

int N, X[MAX_N+1], Y[MAX_N+1];
int wife[MAX_N+1];
int next_on_right[MAX_N+1];

bool cycle_exists(void)
{
for (int start=1; start&lt;=N; start++)
{
int pos = start;
for (int count=0; count&lt;N; count++)
pos = next_on_right[wife[pos]];
if (pos != 0) return true;
}
return false;
}

int solve(void)
{
int i, total=0;
for (i=1; i&lt;=N; i++)
if (wife[i] == 0) break;

// everyone paired?
if (i &gt; N)
{
if (cycle_exists()) return 1;
else return 0;
}

// try pairing i with all possible other wormholes j
for (int j=i+1; j&lt;=N; j++)
if (wife[j] == 0)
{
// try pairing i &amp; j, let recursion continue to
// generate the rest of the solution
wife[i] = j;
wife[j] = i;
total += solve();
wife[i] = wife[j] = 0;
}
}

int main(void)
{
ifstream fin(&quot;wormhole.in&quot;);
fin &gt;&gt; N;
for (int i=1; i&lt;=N; i++) fin &gt;&gt; X[i] &gt;&gt; Y[i];
fin.close();

for (int i=1; i&lt;=N; i++) // set next_on_right[i]...
for (int j=1; j&lt;=N; j++)
if (X[j] &gt; X[i] &amp;&amp; Y[i] == Y[j]) // j right of i...
if (next_on_right[i] == 0 ||
X[j]-X[i] &lt; X[next_on_right[i]]-X[i])
next_on_right[i] = j;

ofstream fout(&quot;wormhole.out&quot;);
fout &lt;&lt; solve() &lt;&lt; &quot;\n&quot;;
fout.close();
return 0;
}

```