#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h> // fixed sized integer
#include <stdbool.h> // booleans

#define INF UINT32_MAX

/********** Kachel definition **********/
typedef struct Tile {
    uint32_t x;
    uint32_t y;
    uint32_t neigh[4]; // Nachbarn
    struct Tile *p_next; // queue
    uint32_t pair; // matching partner
    uint32_t dist; // entfernung zu Knoten 0 im Schichtgraph
} Tile;

// initialisieren des Speichers von einem Tile
void tile_init(Tile *this) {
    memset(this, 0, sizeof(Tile));
    this->dist = INF;
}

int tile_compare(const void *p, const void *q) {
    const Tile *s = (const Tile*) p;
    const Tile *t = (const Tile*) q;
    // als erstes nach x sortieren
    if (s->x < t->x) return -1;
    if (s->x > t->x) return 1;
    // danach nach y sortieren
    if (s->y < t->y) return -1;
    if (s->y > t->y) return 1;
    return 0; // Elemente sind gleich
}

// Kacheln wie im Schachbrettmuster einordnen
uint32_t tile_odd(Tile* this) {
    return ((this->x ^ this->y)&1);
}

/********** Kachelfeld **********/
typedef struct Field {
    // Array von Tiles, tile 0 is imagenary tile for hk-algorithmus
    // Tiles werden mit 1 bis num_tiles exklusive indiziert
    Tile *tiles;
    uint32_t num_tiles;
    uint32_t size;
    uint32_t num_odd;
} Field;

// returns 0 if successful, nonzero if failed
int field_init(Field *this) {
    memset(this, 0, sizeof(Field));
    this->tiles = malloc(sizeof(Tile));
    this->num_tiles = 1;
    this->size = 1;
    return this->tiles == 0;
}

// if an error occurs, all memory get freed
int field_push(Field *this, Tile *p_tile) {
    if (this->size == this->num_tiles) {
        if (this->size == 1u<<31) return 1; // catch overflow
        this->size *= 2; // Armortisiert O(1)
        Tile *new = realloc(this->tiles, this->size*sizeof(Tile));
        if (new == NULL) return 1; // catch failed realloc
        this->tiles = new;
    }
    this->num_odd += tile_odd(p_tile);
    memcpy(this->tiles+this->num_tiles, p_tile, sizeof(Tile));
    this->num_tiles++;
    return 0;
}

/** Parsen einer Kachel(Tile) aus einer Zeile von StdIn
 *
 * Die Werte werden in die uebergebene Kachel geschrieben, sind aber
 * nur gueltig, wenn der Rueckgabewert `ReadOk` ist.
 *
 * Voraussetzung: p_tile muss initialisiert sein
 */
typedef enum ReadResult {
    ReadOk,
    ReadEof,
    ReadErrOverflow,
    ReadErrInvalidChar,
    ReadErrTooFewNumbers,
    ReadErrTooManyNumbers,
    ReadErrOutOfMemory,
} ReadResult;
ReadResult read_line(Tile* p_tile){
    int c = getchar();
    if (c == EOF) {
        return ReadEof;
    }
    int cur_number = 0;
    bool cur_whitespace = true;
    uint32_t *p_cur; // aktuell zu parsende Zahl
    while(1) {
        if ('0' <= c && c <= '9') {
            if (cur_whitespace) {
                if(cur_number == 2) {
                    return ReadErrTooManyNumbers;
                }
                p_cur = (&p_tile->x)+cur_number;
                cur_whitespace = false;
                cur_number++;
            }
            // 429496730 = 2^32 / 10, daher wenn `p_cur` groesser ist, wird ein
            // overflow erzeugt
            if (*p_cur > 429496729) {
                return ReadErrOverflow;
            }
            (*p_cur) *= 10;
            int digit = c - '0';
            if (*p_cur > UINT32_MAX - digit) {
                return ReadErrOverflow;
            }
            (*p_cur) += digit;
        } else if (c == ' ') {
            cur_whitespace = true;
        } else if (c == '\n') {
            if (cur_number == 2) {
                return ReadOk;
            } else {
                return ReadErrTooFewNumbers;
            }
        } else {
            return ReadErrInvalidChar;
        }
        c = getchar(); // get next character
    }
}

/** Liest das Input von StdIn und schreibt das Ergebnis in die uebergebene Liste
 *
 * Laufzeit: O(n)
 * Speicherbedarf: O(n)
 *
 * Return:
 *  - ReadResult:
 *     ReadOk, falls das lesen Erfolgreich war
 *     ReadErr..., falls die Eingabe ungueltig ist oder zu wenig Speicher vorhanden.
 *             `num_tiles` indiziert die Zeile, in der der Fehler aufgetreten ist
 */
ReadResult field_parse(Field *this) {
    while (1) {
        Tile next;
        tile_init(&next);
        ReadResult result = read_line(&next);
        switch (result) {
        case ReadOk:
            // einfuegen in die Liste
            if (field_push(this, &next)) {
                return ReadErrOutOfMemory;
            }
            break;
        case ReadEof:
            if (this->num_tiles == 1) {
                return ReadEof;
            } else {
                return ReadOk;
            }
        default: // error
            return result;
        }
    }
}

/** Setzen der Nachbarn der Kacheln
 * Rueckgabe: 0 falls alles ok
 *            1 falls Dopplungen vorkommen
 */
int field_neighbours(Field *this) {
    uint32_t top = 1; // vergleich mit oberer Zeile
    uint32_t begin_line = 1; // start der aktuellen Zeile
    Tile *t = this->tiles;
    for (uint32_t cur = 2; cur < this->num_tiles; cur++) {
        // ermitteln der x-Beziehung
        uint32_t east = cur-1;
        if (t[cur].x == t[east].x) { // gleiche Zeile
            if (t[cur].y == t[east].y) { // gleiche Spalte
                return 1; // Doppelung
            } else if (t[cur].y-1 == t[east].y) {
                t[cur].neigh[1] = east;
                t[east].neigh[2] = cur;
            }
        } else {
            top = begin_line;
            begin_line = cur; // neue Zeile
        }
        // ermitteln der Zeilen-Beziehung
        if (begin_line != 1 && t[top].x < t[begin_line].x - 1) {
            // Zeilensprung => Warten bis zur naechsten Zeile angekommen
        } else if (t[top].x == t[cur].x - 1) {
            // finden, ob paar nach oben existiert O(n) fuer alle Nachbarn nach oben/unten.
            for(;t[top].y < t[cur].y && top < begin_line; top++);

            // aktuelle obere Kachel koennte benachbart sein
            if (t[top].y == t[cur].y) { // nicht auf naechste Zeile uebergegangen
                // Neue Verbindung oben/unten gefunden
                t[top].neigh[3] = cur;
                t[cur].neigh[0] = top;
            }
        }
    }
    return 0;
}

/********** Schlange von Tiles **********/
typedef struct Queue {
    Tile *p_first;
    Tile *p_last;
} Queue;

void queue_init(Queue* this) {
    this->p_first = NULL;
    this->p_last = NULL;
}

void queue_push(Queue* this, Tile* p_tile) {
    if (this->p_last != NULL) {
        this->p_last->p_next = p_tile;
    } else {
        this->p_first = p_tile;
    }
    this->p_last = p_tile;
    p_tile->p_next = NULL;
}

bool queue_empty(Queue* this) {
    return this->p_first == NULL;
}

Tile *queue_pop(Queue* this) {
    Tile *p_tile = this->p_first;
    this->p_first = p_tile->p_next;
    if (this->p_first == NULL) {
        this->p_last = NULL;
    }
    return p_tile;
}

/********** Algorithmus von Hopcroft und Karp **********/
bool hk_bfs(Field *this) {
    Queue q; // Schlange von Kacheln
    queue_init(&q);
    Tile *t = this->tiles;
    for (uint32_t i = 1; i < this->num_tiles; i++) {
        // nur gerade Kacheln werden zur queue hinzufuegen
        if (tile_odd(&t[i])) {
            continue;
        }
        if (t[i].pair == 0) {
            t[i].dist = 0;
            queue_push(&q, &t[i]);
        } else {
            t[i].dist = INF;
        }
    }
    t[0].dist = INF;
    while (!queue_empty(&q)) {
        Tile *e = queue_pop(&q); // nehme naechste gerade Kachel
        if (e->dist >= t[0].dist)
            continue;
        for (int i = 0; i < 4; i++) {
            Tile* p_neigh = &t[e->neigh[i]];
            Tile* p_pair = &t[p_neigh->pair];
            if(p_pair->dist == INF) {
                p_pair->dist = e->dist+1;
                queue_push(&q, p_pair);
            }
        }
    }
    return t[0].dist != INF;
}

bool hk_dfs(Field *this, uint32_t e) {
    if (e == 0)
        return true;
    Tile *t = this->tiles;
    Tile *p_even = &t[e];
    for (int i = 0; i < 4; i++) {
        // Benachbart zu e
        uint32_t o = p_even->neigh[i]; // Nachbar, ungerade Kachel
        Tile* p_odd = &t[o];
        if (t[p_odd->pair].dist == p_even->dist+1) {
            // Augmentiere den Pfad, falls durch Tiefensuche gefunden
            if (hk_dfs(this, p_odd->pair)) {
                p_even->pair = o;
                p_odd->pair = e;
                return true;
            }
        }
    }
    // Kein augmentierender Pfad von e aus
    p_even->dist = INF;
    return false;
}

void hk_print(Field *this) {
    Tile *t = this->tiles;
    for (uint32_t i = 1; i < this->num_tiles; i++) {
        if (t[i].pair == 0) {
            // Es ex. nur eine Belegung, wenn alle Knoten gemached wurden
            printf("None\n");
            return;
        }
    }
    for (uint32_t i = 1; i < this->num_tiles; i++) {
        if (tile_odd(&t[i]))
            continue;
        // Gebe nur den machingpartner von der Haelfte der Knoten aus um
        // Doppelungen zu vermeiden
        uint32_t p = t[i].pair;
        printf("%u %u;%u %u\n", t[i].x, t[i].y, t[p].x, t[p].y);
    }
}

void hk(Field *this) {
    while(hk_bfs(this)) {
        for (uint32_t i = 1; i < this->num_tiles; i++) {
            if (tile_odd(&this->tiles[i]))
                continue;
            // Starte Augmentation nur von Knoten, die noch nicht gemached sind
            if (this->tiles[i].pair == 0)
                hk_dfs(this, i);
        }
    }
    hk_print(this);
}

int main() {
    Field f;
    if(field_init(&f)) {
        fprintf(stderr, "Failed to allocate memory");
        return EXIT_FAILURE;
    }
    int result = EXIT_FAILURE;
    switch(field_parse(&f)) {
    case ReadOk:
        qsort(f.tiles+1, f.num_tiles-1, sizeof(Tile), tile_compare);
        if (field_neighbours(&f) != 0) {
            fprintf(stderr, "Error: Duplicated entry\n"); // Duplikat exisitert
            break;
        }

        if (f.num_tiles - f.num_odd == f.num_odd) {
            printf("None\n");
            break;
        }
        hk(&f); // Algorithmus von Hopcroft und Karp
        result = EXIT_SUCCESS;
        break;
    case ReadEof:               result = EXIT_SUCCESS; break;
    // Fehlerausgabe
    case ReadErrOverflow:       fprintf(stderr, "%u: too big integer\n", f.num_tiles); break;
    case ReadErrInvalidChar:    fprintf(stderr, "%u: invalid character\n", f.num_tiles); break;
    case ReadErrTooFewNumbers:  fprintf(stderr, "%u: too few numbers\n", f.num_tiles); break;
    case ReadErrTooManyNumbers: fprintf(stderr, "%u: too many numbers\n", f.num_tiles); break;
    case ReadErrOutOfMemory:    fprintf(stderr, "%u: not enough memory\n", f.num_tiles); break;
    }
    free(f.tiles);
    return result;
}