#!/usr/bin/php -f
<?
        class Kante {
                var $ecken;
                var $done;

                function Kante($a, $b) {
                        $this->ecken = array($a, $b);
                        $this->reset();
                }

                function getEcke($i) {
                        return $this->ecken[$i];
                }

                function reset() {
                        $this->done = false;
                }

                function set() {
                        $old = $this->done;
                        $this->done = true;

                        return $old;
                }
        }

        class Ecke {
                var $kanten;

                function Ecke() {
                        $this->kanten = array();
                }

                function addKante($kante, $index) {
                        $this->kanten[$kante] = $index;
                }

                function getKanten() {
                        return $this->kanten;
                }
        }

        class Netzwerk {
                var $kanten;
                var $ecken;

                function Netzwerk($list) {
                        $this->kanten = $list;

                        $this->ecken = array();
                        foreach($this->kanten as $ki => $kante) {
                                for($i = 0; $i < 2; $i++) {
                                        $ei = $this->kanten[$ki]->getEcke($i);
                                        if (!isset($this->ecken[$ei]))
                                                $this->ecken[$ei] = new Ecke();
                                        $this->ecken[$ei]->addKante($ki, $i);
                                }
                        }
                }

                function reset() {
                        foreach($this->kanten as $ki => $kante)
                                $this->kanten[$ki]->reset();
                }

                function __solve($rem, $ei) {
                        if (!$rem)
                                return array($ei);

                        $kanten = $this->ecken[$ei]->getKanten();
                        foreach($kanten as $ki => $i) {
                                if ($this->kanten[$ki]->set())
                                        continue;

                                $r = $this->__solve($rem - 1,
                                        $this->kanten[$ki]->getEcke(1 - $i));
                                if (!($r === false)) {
                                        array_push($r, $ei);
                                        return $r;
                                }

                                $this->kanten[$ki]->reset();
                        }

                        return false;
                }

                function solve() {
                        $this->reset();

                        foreach(array_keys($this->ecken) as $ei) {
                                $r = $this->__solve(count($this->kanten), $ei);
                                if (!($r === false))
                                        return $r;
                        }

                        return false;
                }
        }

        /*
         *       1           2
         *
         *
         * 3           4           5
         *
         *
         *
         * 6           7           8
         */

        $doppelhaus = array(
                new Kante(1, 3),
                new Kante(1, 4),
                new Kante(2, 4),
                new Kante(2, 5),
                new Kante(3, 4),
                new Kante(4, 5),
                new Kante(3, 6),
                new Kante(4, 7),
                new Kante(5, 8),
                new Kante(6, 7),
                new Kante(7, 8),
                new Kante(3, 7),
                new Kante(4, 6),
                new Kante(4, 8),
                new Kante(5, 7)
        );

        /*
         *       1
         *
         *
         * 2           3
         *
         *
         *
         * 4           5
         */

        $einzelhaus = array(
                new Kante(1, 2),
                new Kante(1, 3),
                new Kante(2, 3),
                new Kante(2, 4),
                new Kante(3, 5),
                new Kante(4, 5),
                new Kante(2, 5),
                new Kante(3, 4)
        );

        $netzwerk = new Netzwerk($doppelhaus);
//      $netzwerk = new Netzwerk($einzelhaus);

        $r = $netzwerk->solve();

        print_r($r);
?>