/* KSP 15-1-2
 * Vlacky
 *
 * Petr Baudis
 * Rocnik: 3
 * Skola: Ad Fontes
 */


/*
 * Vstup:
 * stanoviste1 kolej1 stanoviste2 kolej2 * N
 *
 * Vystup:
 * popis moznych tras
 *
 * Algoritmus:
 *
 * Kudy povedou ktere trasy budeme urcovat na zaklade hodnot, kterymi ocenime
 * jednotlive uzly - takove hodnoty by zejmena mely reflektovat, kolik moznych
 * tras by danym uzlem mohlo maximalne vest - kazdy uzel bude mit tedy jako
 * hodnotu soucet hodnot vsech uzlu, ze kterych do nej vedou koleje. Pocatecni
 * uzly pak budou mit hodnotu inicializovanou na 1.
 *
 * Pri vyhledavani tras si pak vzdy jako nasledujici uzel vybereme ten nejmene
 * konfliktni (s nejmensi vahou), takze se nam vedle sebe vzdy nasklada
 * maximalni mozny pocet tras (protoze bude minimum konfliktu). Ovsem na to je
 * treba, abychom i nejakym zpusobem "videli do budoucnosti", tedy pri
 * pokracovani kterou vetvi se vyskytne kolik konfliktu. Proto po spocitani vah
 * vsech uzlu zustaneme na druhem konci grafu, a pro kazdy uzel prepocitame
 * vahu jako maximum z vah uzlu, do kterych vedou z daneho uzlu koleje. Pak
 * staci od opet od zacatku grafu zacit postupne stavet trasy - vzdy si jako
 * nasledujici uzel (vcetne uzlu startovniho) vybereme takovy, ktery jsme jeste
 * nenavstivili a ktery ma nejmensi vahu.
 *
 * V pameti si musime ulozit cely graf a pouze tento graf, tedy pametova
 * narocnost jest O(N). Pri nastavovani vah projdeme cely graf dvakrat (jednou
 * nastavime vahy podle souctu, a pak jdeme zpet a nastavujeme vahy na maxima),
 * pri hledani tras pak take cely graf projdeme prave jednou - to jest 3N. Ovsem
 * behem druheho pruchodu (kdy jsou jiz ustalene hodnoty) si budeme muset
 * postavit z uzlu haldu (tedy slozitost bude 2N + N*log(N)), tedy casova
 * narocnost je O(N*log(N)) (pro extremni pripad kdy vsechny hrany vychazeji z
 * jednoho uzlu).
 *
 * Implementace pocita s tim, ze graf neni orientovany (podobne jako na diagramu
 * prilozenemu k zadani), tedy vsechny cesty vedou do Rima^W^Hpredu. Algoritmus
 * samotny by mel zvladnout i klikate koleje ;-).
 */


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

/* Misto staticky alokovanych poli si prosim predstavte neco rozumneho (tedy
 * nejake pole dynamicke) - tohle je zde pro jednoduchost. */

/* Ok, mozna ze ty nazvy jsou krapet delsi nez obvykle.. ;-) */

struct rail_end {
  int checkpoint, crossing;
};

struct crossing {
  struct rail_end self;
  struct rail_end rails_in[10], rails_out[10];
  int rails_in_no, rails_out_no;
  heap *rails_out_heap;
  int weight; /* 0 -> N/A */
  int visited;
};

struct checkpoint {
  struct crossing crossings[10];
};

/* checkpoint 0 je specialni, je to fyzicky jediny pocatecni uzel, ale slouzi
 * nam jako jakysi genericky container na pocatecni uzly.. */
static struct checkpoint checkpoints[100];
static int ch_max;


int
main() {
  struct rail_end *re, *re2;
  int ch;

  /* Nacti data.. */

  while (!feof(stdin)) {
    int ch1 = 0, cr1 = 0, ch2 = 0, cr2 = 0;

    scanf("%d %d %d %d", &ch1, &cr1, &ch2, &cr2);

    checkpoints[ch1].crossings[cr1].weight = 1;
    checkpoints[ch1].crossings[cr1].rails_out[
      checkpoints[ch1].crossings[cr1].rails_out_no].checkpoint = ch2;
    checkpoints[ch1].crossings[cr1].rails_out[
      checkpoints[ch1].crossings[cr1].rails_out_no].crossing = cr2;
    checkpoints[ch1].crossings[cr1].rails_out_no++;

    checkpoints[ch2].crossings[cr2].weight = 1;
    checkpoints[ch2].crossings[cr2].rails_in[
      checkpoints[ch2].crossings[cr2].rails_in_no].checkpoint = ch1;
    checkpoints[ch2].crossings[cr2].rails_in[
      checkpoints[ch2].crossings[cr2].rails_in_no].crossing = cr1;
    checkpoints[ch2].crossings[cr2].rails_in_no++;

    if (ch_max < ch1) ch_max = ch1;
    if (ch_max < ch2) ch_max = ch2;
  }

  /* Nastav vahy smerem dopredu.. */
  /* Bereme poprade checkpoint po checkpointu, crossing po crossingu. */

  for (ch = 1; ch <= ch_max; ch++) {
    int cr;

    for (cr = 0; cr < 10; cr++) {
      int rails;
      int sum = 0;

      /* I kdyz to tu je de facto zbytecne... */
      if (!checkpoints[ch].crossings[cr].weight)
	continue;

      checkpoints[ch].crossings[cr].self.checkpoint = ch;
      checkpoints[ch].crossings[cr].self.crossing = cr;

      for (rails = 0; rails < checkpoints[ch].crossings[cr].rails_in_no; rails++) {
	sum +=
          checkpoints[checkpoints[ch].crossings[cr].rails_in[rails].checkpoint].
            crossings[checkpoints[ch].crossings[cr].rails_in[rails].crossing].weight;
      }

      if (sum) {
        checkpoints[ch].crossings[cr].weight = sum;
	//printf("(%d,%d) -> %d\n", ch, cr, sum);
      } else {
        /* chceme nechat jednicku */
      }
    }
  }

  /* Rozpropaguj maximalni vahy zpet.. */

  for (ch = ch_max; ch >= 1; ch--) {
    int cr;

    for (cr = 0; cr < 10; cr++) {
      int rails;
      int max = 0;

      if (!checkpoints[ch].crossings[cr].weight)
	continue;

      for (rails = 0; rails < checkpoints[ch].crossings[cr].rails_out_no; rails++) {
        /* abych si usetril psani */
	int nmax =
          checkpoints[checkpoints[ch].crossings[cr].rails_out[rails].checkpoint].
            crossings[checkpoints[ch].crossings[cr].rails_out[rails].crossing].weight;

	heap_add(
	  &checkpoints[ch].crossings[cr].rails_out_heap,
          &checkpoints[checkpoints[ch].crossings[cr].rails_out[rails].checkpoint].
            crossings[checkpoints[ch].crossings[cr].rails_out[rails].crossing].self,
	  nmax);

        if (nmax > max) max = nmax;
      }

      if (max) {
        checkpoints[ch].crossings[cr].weight = max;
	//printf("(%d,%d) => %d\n", ch, cr, max);
      }
      /* else { z uzlu nevedou zadne koleje, tudiz je jeho vaha jiz finalni } */

      /* Vaha uzlu uz je definitivni, takze muzeme nastrkat vsechny svoje
       * reference do relevantnich hald. */

      if (!checkpoints[ch].crossings[cr].rails_in_no) {
	/* Zadne vstupni koleje => startovni uzel => nadratovat do meta-uzlu. */
	/* To nadratovani neni uplne korektni, protoze nenadratujeme meta-uzel do
	 * startovniho uzlu, ale to by nam ted melo byt jedno. */
	heap_add(
	  &checkpoints[0].crossings[0].rails_out_heap,
	  &checkpoints[ch].crossings[cr].self,
	  checkpoints[ch].crossings[cr].weight);
      }
    }
  }

  /* Postav trasy.. */

  while ((re = heap_fetch(&checkpoints[0].crossings[0].rails_out_heap))) {
    int skip = 0;

    heap_shift(&checkpoints[0].crossings[0].rails_out_heap);

    printf("(%d,%d)", re->checkpoint, re->crossing);

    while ((re2 = heap_fetch(&checkpoints[re->checkpoint].
	                     crossings[re->crossing].rails_out_heap))) {
      heap_shift(&checkpoints[re->checkpoint].crossings[re->crossing].rails_out_heap);

      if (checkpoints[re2->checkpoint].crossings[re2->crossing].visited) {
	skip++;
	continue;
      }
      checkpoints[re2->checkpoint].crossings[re2->crossing].visited = 1;
      re = re2;
      skip = 0;

      printf(" -> (%d,%d)", re->checkpoint, re->crossing);
    }

    if (skip)
      printf(" no way");

    printf("\n");
  }

  return 0;
}