#include <stdio.h>
#include <stdlib.h>

int *R;			// Čísla pravých konců

void test(int la, int lb,	// Úsek levých konců
   int ra, int rb,		// Úsek pravých konců
   int on, int flag)		// Připojeno (teď resp. alespoň jednou)
{
   int k;			// Dělící bod
   int a, b, c;			// Pomocné

   if (la > lb || ra > rb)	// S~jistotou nepřipojeno?
      return;
   if (la == lb && ra == rb)	// Triviální případ?
      {
         if (!flag)
            {
               On(la);
               if (!Measure(ra))	// Přerušeno
                  return;
            }
         printf("%d -> %d\n", la, R[ra]);
         return;
      }

   k = (la + lb) / 2;			// Testovací situace
   if (on)
      for(a=k+1; a<=lb; a++)
         Off(a);
   else
      for(a=la; a<=k; a++)
         On(a);

   b = rb+1;			// Konec úseku pravých konců bez napětí
   a = ra;			// Testujeme (``rozděl'')
   while (a<b)
      if (Measure(R[a]))	// Zapojen -- nechat tam, kde je
         a++;
      else
         {
            b--;
            c = R[a];		// Nezapojen -- vyměnit
            R[a] = R[b];
            R[b] = c;
         }

   test(la, k, ra, b-1, 1, 1);	// A panuj\dots
   test(k+1, lb, b, rb, 0, flag);
}

int main(void)
{
int N,i ;
   printf("Počet drátů? ");
   scanf("%d", &N);
   R = malloc(sizeof(int) * N), R--;
   for(i=1; i<=N; i++)
      R[i] = i;
   test(1, N, 1, N, 0, 0);
}