Submission #10301461

---

Source Code Expand

/*
                                                                                                                                                `
                                                                                                                                                `
                                                                                                                                                `
                                                                                                                                                `
                                                                                                                                                `
                                                                                                                                                `
                                                                                                                                                `
                                                                                                                                                `
                                                                         `!!!;'                                                                 `
                                                           '%$@########################&&%:.                                                    `
                                                       .%###################################%.                                                  `
                                                    .`|######################################%                                                  `
                                                 .!@###############################################$'                                           `
                                              .!@#########################@@@#########################&;.                                       `
                                             :@##################@@@&&@@@$!!%&@@@@@@@###################&'                                      `
                                          :&################@@@&$%%||||!!:'':;!!||%|!%&@@#################%`                                    `
                                         |###############@@&&$%|!;;::::':'''':::;;!!|%%%$&&@###############$`                                   `
                                      :&#############@&$%||||!;'````````````'''```'':::'':!|$@@###############;                                 `
                                    :@#############@$$%|!;;;;:'``````...```...`...`'':::''';|%$$$&############&'                                `
                                   |##############&$$$%||!!;:'`````..````....`...```''::::;!!||$&&@@###########&'                               `
                                 !##############@$%|!!!;::'''`````...``.....`````````'''::::;;::!|%$&############|                              `
                                :@##########@&%!:'`::;;:'``....```.......  .``....````````````'':;!|%$@############;                            `
                               ;##########@%;```...`'''`...  .....    ................   .`.    `:!!!!%%%&#########|                            `
                              ;##########&|:.`'`. ..`...   .......   .....  ..  .....   ...   .'':!!:.`''!@#########|.                          `
                              !##########|'`.;!`       .  ......          ..    .      ....  .::'`. .. .`'|@########@:                          `
                              ;##########%'`'%!    ..       .  .                ..    .```.   ';:`..``.`':|@########@:                          `
                              !##########$:;$&;                     . `|%;.  `;||;::`.``';;.  .;!: `;:`';|$#########@!.                         `
                              !##########@$&@|. ...... .`':!|;` !$|%%'!##$' `|####$:`:;:!&$:. '$&!';!!||%&############;                         `
                             `$#############&:  `!!'`:;;;||%@&!'!&&$;.|##%`.|#####%`'$@$&##%` .:||;;;;%@##############!                         `
                             :@#############|. .!&@|;%@@@@@&@@#@&@#@&@############@@#####@:   .`'%@%!!&###############!                         `
                             :@############@;   :&@!;$###@|%|!$@@######################@%`    .;|!;!|%@###############!                         `
                             :@############@:   `$#$%#@@##&@################@$$$&$%|!'       `%#@|;':|&###############!                         `
                              !##########@$%:    |####@&######$;.                          ..`'`      ;@##############!                         `
                              !##########!       ;#########|.                             `;`         ;###############!                         `
                              ;##########;       `%######;                           '$###&:          `%@############&'                         `
                               !########@:       .'.       .:;`                   .|%:                   !##########&'                          `
                               !########@:                                                               ;#########@:                           `
                                !######%.     !##&;.        .                  `%&!`             '&###&' !#########!                            `
                                |#######;.%###!                 `!&###@|;;%@###%.    ';;|&$:;;`     |#%. .%###%$###!                            `
                               !#######|  `%#&'    |##&$####&:     !##########;    `%#####%.!#|.   .%@:   ;###;`%##!                            `
                                !#$!$##!   :@#!        .|###$'.    ;##|.  :&#@;    .``::`          ;@|.   :@#@: `$#|                            `
                                :&&|&##;   :&#!                   :&##;    .%##!                   !&'    ;@##!  |#!                            `
                                 |@@##@;  .`%#!                  '$##;      ;##$`                 :@!    .|##@; :&!                             `
                                 !&|&##%:'.  :&!                :@#%.        .%##;               |&!.   `|@!   `$!                              `
                                 '$%%###&;.   '&&'            `%##&'           |##@&:    ...;&&&@;     .;&#|':;$&:                              `
                                 .|######&;        '$@@@@@@@@#|                                        :&######%`                               `
                                   !#####&:                                                           '$#####@:                                 `
                                   '$#####@:                                                          ;#####$`                                  `
                                     '&####%.                 ``                                     '$#####;                                   `
                                      !#####$'                |@:  .:%|;;;;!$#####@#|               '&###$:                                     `
                                       :&####&:               ;####################@:    ':`       `%###@:                                      `
                                         ;#####@%:.                                         `'';|@######$`                                      `
                                         `$######@|`                                        !#&||@#####$`                                       `
                                          :&######@%'.                        .`''''` .';!|%@#@$$@####&:                                        `
                                           |######@|'.   ;##$!!%@##########################@:   '$####;                                         `
                                           :&#####$;''.`%#########&'             `|@$:         .%###@;                                          `
                                            :@####@;          |#@##&$;         `|%'           .|####!                                           `
                                              !####@;                                .        |####!                                            `
                                               :@###@|`         .                 `|!.       |####%.                                            `
                                                .|####!          `;$@%|!!!!!%&&@#$;.        !#####|                                             `
                                                .%####&:              '%&@@@|`             '&#####|                                             `
                                                .%#####|.                                 :&######%`                                            `
                                       :|||;`    !#######;                              .%#####@@#####@$;.                                      `
                                   `$#############&%!%#####|.                         :@####%:..'!&######@;                                     `
                                  `$#############|`..'%#######!                      ;####&;.    .'%#######!                                    `
                                .|##############@!`    .'%#########%'.          '%#####%`           :@#######@%;:.                              `
                          ;%|;. !############%::;'        `!&############@&&@#######@%'               !###########&'                            `
                         !################$'   .:'         '|&######################$:.               :@#############@@@@@@;                    `
                      ';$##&;:&###########$`                  :|$@################%:.                 !#####################@;                  `
                   '%####@$!:.  `%#########!                    .:!%&@#######@%!;'.                   |##############%!$@####!                  `
                .|#######&;'. .    |#######%.                      .':;!!!!!!;`...                   .|############|. :$@@####%.                `
                !####&$&@#@!:'.       ;#####%`                  .`';;'... ..''``.                    !##########%`    ''':$######$`             `
                ;#####@$$;`%&:.         `%####;                   .:;;:'':;||!:`                    !#########!          :&#@@####!             `
          '%######@######!   !!            :$@$`                    ...`.'::`..                   '$######@!`         '|$$&!!@#######@!.        `
     '$#########@&$$@######@:    ;: . `'    ....                      ...``.                    `$######&'           '!;`'!@######&&########$'  `
  ;############@#@@@@@$|%@###$`  `!!.;' .     :!.                                             .%#####!.            .;::&####|`..`  ..;@########!'
  |########&|;'``..`:'    ..!##%:.    ;;      `.                                            .|###|`             `'|###@&$|`  ..   .`|&&@#######%:
  |###@#@@#&|:`.`';;:;!!!;:;''!$##&;'.  .'%; .;&###&|$!                                     '$; .|$:;|`   ...;&###$'    ....      :||%&########%:
  |#######@$;!%%:```           .!@###&|`   :|'!########@#!                                ;@! :@####%'. `|@###&:         ..`:::%$$&$$$&@##@@@##|:
  |########$;::'`         .`.     `%#####%!: .. !#####%` !#%.                        !; '%; !#############&:          `::`.```. .':.  :$@&&&###|:
  !####@%:::;;:::::` .........            '.  !#######%;;';; `%#&'             ;&: `;``$@!%########&&##&|::::'.             ':.     `!%@@######|:
  !#####%;;::.       ...... ....`..  ..  '::!|&########$';%`.'` .;%:        !#$';$%|&$!&##########$'        `';;;;!&##&%||||||%;`   .:|&###@###|:
  |#######|`...      `|$&&$$!`....           ;$:  :&#@:     `'''``.   .%########&'  .%#@&$%$#####$`     ....`:%&@@@@@@&&@@!`.      .`'%@#######|'
  |######@@$:       .`..`!@&$&&&&:                ;@#######@@#$%@######&$;    '%@##%!@###@&&@####%.     `!&@@@@@$:..`..``.``...     `|&####@@##!'
  ;###&|;::!&#&%%%%:         .'::::;|$&&$%|'..;%%&#######%;$########@&#####%`   '|@###;    '%####$;::::::`            '!|%%%%%%%%%&#$:'::.'%###|'
  `%###@|;|%$%$@#&|;::::`          '|%%%%%$%|%|;';$##@|'.   |######&'     .:|$%: :&@|'.     !####%.              `::;:!$@######&%%%%%!'  ':;&##|:
  '$##%:.    :&##@####@$;.  ..                    `$|     :; !#####|      '|%:  ``    ...   !####!          .  ..:&#@@@@##@&||$;         :&####|'
  !####&@@&;        ...`.'%@##@@#@@&!`            :&&!.       !###&'  :||:.`   !%'     ``:$######@@@&&@@@&@##$;``....             |@@@@########!'
  !#######@$||!:          ';!;;;!&###&|||||||||||%&##@!`.     !###&||%!!!:   .:;`        `;;%####$;:;;;;;;;;;;;::.         '||||||&#####%!;;$##!`
  `%#&:.`:!||||||%@#@%;::;;;'                     ;@@:    .. .%###|.   `:::'  .:!;'`':'`   `$####!             ':;;;;!%@@&%%%|;`        `;%&###|:
  .%##|..       '$##@@@@@@#&:...`..              `$#$'        !##%`   ..`.`:%@@! '%@$:''. .`|####|... .........`:%###@#@@@|`        ....`%#####|:
  !###@&!       .`.```':!&##@&&&&$:              '&#%.        !#&'     ````.    .```:%&&&&&@#####@!':|$&&$&&&&&&&&&@##|`````.       !@@@#######!'
  :&#########@$||||:            `::::;;;;;!!;;;:;$###$'  .'`  |#@|.  .:;;:.                `%####%:''':::::`               `!||&##$;;;:::.  ;##|:
  .%#@$%$%%%%%$@###$::::::'.           ...`;|!::!&##@$%|||!' .%##&%%$%'        `'.         :&####!                  .':::'::%@&$%%!` .!!':;$###%:
  :&#############@|.              .  '$##################&;..!@###@#######%'.             .!#####!          .              `$#####@|``;&|!&####|:
  |####&%'   .''''':|@###@$$$$$$%;.             |####%`      .|#@;.         .;$$$%$&$$$$$$&######$:..:|%$$$$$$$&&&&@######&;'''.    ;$&########|:
  |#######@%;;`    '!|!||$#######&|!!!;;;!!!;`.!#####@: .;|!!|&#$'   `:'':;;$######################################%!|!!!!!;.  .`;|&######@####%:
  |############$!''''..';$&&&&@########################$;'!;`:@#&:``'|$@######@@@@&&&&&&&@#######@&&&&&&&&&&&@@&&&&$|:.    .`''$########@&@####%:
  |###&%$&#################@%;'  ..      `|@############$: `%@###########$`  `%%:.     . :@######|         !#####################@$%&##########%:
  |#######################################@&&@######################@@&@#######################################################################%:
*/

#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

inline char gc() {
    static const int L = 233333;
    static char sxd[L], *sss = sxd, *ttt = sxd;
    if (sss == ttt) {
        ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
        if (sss == ttt) {
            return EOF;
        }
    }
    return *sss++;
}

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
    char dd;
    for (; !isalpha(c); dd);
    return c;
}

inline char readchar() {
    char dd;
    for (; c == ' '; dd);
    return c;
}

template <class T>
inline bool read(T& x) {
    bool flg = false;
    char dd;
    x = 0;
    for (; !isdigit(c); dd) {
        if (c == '-') {
            flg = true;
        } else if(c == EOF) {
            return false;
        }
    }
    for (; isdigit(c); dd) {
        x = (x * 10) + (c ^ 48);
    }
    if (flg) {
        x = -x;
    }
    return true;
}
#undef dd

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) {
        putchar(x | 48);
        return;
    }
    write(x / 10);
    putchar((x % 10) | 48);
}

template <class T>
inline void writesp(T x) {
    write(x);
    putchar(' ');
}

template <class T>
inline void writeln(T x) {
    write(x);
    puts("");
}

#define lowbit(x) (x & -x)

namespace dfcmd {
    const int maxn = 200005;
    const int inf = 0x3f3f3f3f;

    struct Edge {
        int to, nxt, flow;
    } e[maxn * 10];

    int first[maxn];
    int first_bak[maxn];

    inline void add_edge(int from, int to) {
        // cout << "edge    " << from << ' ' << to << endl;
        static int cnt = -1;
        e[++cnt].nxt = first[from];
        first[from] = cnt;
        e[cnt].to = to;
        e[cnt].flow = 1;
        // cout << "edggg " << cnt << ' ' << from << ' ' << first[from] << ' ' << e[cnt].flow << endl;
        e[++cnt].nxt = first[to];
        first[to] = cnt;
        e[cnt].to = from;
        e[cnt].flow = 0;
    }

    int n, nn, S, T;
    vector<int> dian[maxn];
    vector<int> too[maxn];

    int dep[maxn];

    inline bool bfs() {
        for (int i = 1; i <= n << 1; ++i) {
            first[i] = first_bak[i];
        }
        queue<int> q;
        memset(dep, 0, sizeof(dep));
        dep[S] = 1;
        q.push(S);
        while (!q.empty()) {
            int now = q.front();
            // cout << "now = " << now << ' ' << first[now] << endl;
            q.pop();
            for (int i = first[now]; ~i; i = e[i].nxt) {
                int to = e[i].to;
                // cout << i << ' ' << e[i].to << ' ' << e[i].flow << endl;
                if (!dep[to] && e[i].flow) {
                    dep[to] = dep[now] + 1;
                    q.push(to);
                }
            }
        }
        return dep[T];
    }

    inline int dfs(int now, int all) {
        if (now == T) {
            return all;
        }
        int flow = 0;
        for (int i = first[now]; ~i; i = e[i].nxt) {
            first[now] = i;
            int to = e[i].to, f;
            if (e[i].flow && dep[to] == dep[now] + 1 && (f = dfs(to, min(e[i].flow, all)))) {
                all -= f;
                flow += f;
                e[i].flow -= f;
                e[i ^ 1].flow += f;
            }
        }
        return flow;
    }

    inline int Dinic() {
        int ans = 0;
        while (bfs()) {
            ans += dfs(S, inf);
        }
        return ans;
    }

    int pp[maxn];
    bool viss[maxn];
    pair<int, int> ee[maxn];

    inline int getans() {
        for (int now = 1; now < n; ++now) {
            for (int i = first[now]; ~i; i = e[i].nxt) {
                int to = e[i].to;
                if (!e[i].flow) {
                    pp[now] = to;
                    pp[to] = now;
                    break;
                }
            }
        }
        queue<int> q;
        while (!q.empty()) {
            q.pop();
        }
        q.push(n);
        memset(viss, 0, sizeof(viss));
        viss[n] = true;
        int ans = 0;
        while (!q.empty()) {
            int now = q.front();
            // cout << "now = " << now << endl;
            q.pop();
            for (auto jh : too[now]) {
                if (!viss[pp[jh]]) {
                    /*
                    if (!pp[jh]) {
                        cout << jh << endl;
                    }
                    */
                    viss[pp[jh]] = true;
                    ee[jh] = make_pair(now, pp[jh]);
                    ans++;
                    q.push(pp[jh]);
                }
            }
        }
        return ans;
    }

    int Main() {
        // freopen("a.in", "r", stdin);
        read(n);
        memset(first, 0xff, sizeof(first));
        for (int i = 1, cnt, xx; i < n; ++i) {
            read(cnt);
            while (cnt--) {
                read(xx);
                dian[i + n - 1].push_back(xx);
                too[xx].push_back(i + n - 1);
                if (xx != n) {
                    add_edge(xx, i + n - 1);
                }
            }
        }
        nn = (n - 1) << 1;
        S = ++nn, T = ++nn;
        for (int i = 1; i < n; ++i) {
            add_edge(S, i);
        }
        for (int i = 1; i < n; ++i) {
            add_edge(i + n - 1, T);
        }
        for (int i = 1; i <= n << 1; ++i) {
            first_bak[i] = first[i];
        }
        int ff = Dinic();
        if (ff != n - 1) {
            puts("-1");
            return 0;
        }
        // cout << ff << endl;
        if (getans() != n - 1) {
            puts("-1");
            return 0;
        }
        for (int i = 1; i < n; ++i) {
            // assert(ee[i + n - 1].first), assert(ee[i + n - 1].second), assert(ee[i + n - 1].first != ee[i + n - 1].second);
            writesp(ee[i + n - 1].first), writeln(ee[i + n - 1].second);
        }
        return 0;
    }
}

int main() {
    return dfcmd::Main();
}

Submission Info

Judge Result