#include "common.h"

#define UNENGAGED -1

int main(int ac, char *av[])
{
    int candidate, n, i, j;
    int *men_status, *women_status, *women_suitor_rank;
    int **men_preferences, **women_preferences, **men_proposed, **women_proposed;
#ifdef DEBUG
    int round = 0;
#endif

    scanf("%d", &n);
    if (n < 0)
        ERR_MESG("Invalid value of n");
    matrix_alloc(men_preferences, n, n, int);
    matrix_alloc(women_preferences, n, n, int);
    matrix_alloc(men_proposed, n, n, int);
    matrix_alloc(women_proposed, n, n, int);

    if (NULL == (men_status = Malloc(n, int)) ||
        NULL == (women_status = Malloc(n, int)) ||
        NULL == (women_suitor_rank = Malloc(n, int)))
        ERR_MESG("stable-marriage: out of memory");

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &men_preferences[i][j]);
            men_preferences[i][j] -= n;
        }
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &women_preferences[i][j]);
        }
    }

#if 0
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", men_preferences[i][j] + n);
        }
        putchar('\n');
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", women_preferences[i][j]);
        }
        putchar('\n');
    }
#endif // DEBUG

    for (i = 0; i < n; i++) {
        men_status[i] = women_status[i] = UNENGAGED;
        women_suitor_rank[i] = n;
        for (j = 0; j < n; j++) {
            men_proposed[i][j] = 0; // whether i-th man has proposed to j-th woman
            women_proposed[i][j] = 0; // whether j-th man has proposed in the current round to i-th woman
        }
    }

    while (1) {
        /* Clear the list of proposals received by each woman IN THIS ROUND */
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                women_proposed[i][j] = 0;

        for (i = 0; i < n; i++) { /* for each man */
            if (men_status[i] != UNENGAGED)
                continue;
            /* who do I prefer the most? */
            for (j = 0; j < n; j++) {
                candidate = men_preferences[i][j];
                if (men_proposed[i][candidate] == 0)
                    break;
            }
            if (j < n) {
                /* found someone to propose to; propose to her */
                men_proposed[i][candidate] = 1;
                women_proposed[candidate][i] = 1;
            }
        }

        /* For each woman, find if there is any scope for improvement */
        for (i = 0; i < n; i++) {
            for (j = 0; j < women_suitor_rank[i]; j++) {
                candidate = women_preferences[i][j];
                if (women_proposed[i][candidate])
                    /* found somebody better than my current */
                    break;
            }
            if (j < women_suitor_rank[i]) { // ditch earlier suitor
                men_status[candidate] = i;
                if (women_status[i] != UNENGAGED)
                    men_status[women_status[i]] = UNENGAGED;
                women_status[i] = candidate;
                women_suitor_rank[i] = j;
            }
        }

#ifdef DEBUG
        printf("After round %d\n", ++round);
        for (i = 0; i < n; i++)
            printf("%d %d\n", i, men_status[i] + n);
        sleep(10);
#endif
        /* Check whether done */
        for (i = 0; i < n; i++) {
            if (men_status[i] == UNENGAGED)
                break;
        }
        if (i == n) // all engaged
            break;
    }

    for (i = 0; i < n; i++)
        printf("%d %d\n", n+i, women_status[i]);

    matrix_free(men_preferences);
    matrix_free(women_preferences);
    matrix_free(men_proposed); matrix_free(women_proposed);
    free(men_status); free(women_status);

    return 0;
}