program sveciai_is_Japonijos;
  { 172 u‘davinys }
  { Hopkrofto-Karpo algoritmas }

  const MAX_M = 50;   { max(|K|, |D|) }
        PR = 'JAPON9.DAT';
        RZ = 'JAPON9.REZ';
  type lentele = array [0..2*MAX_M] of integer;
       grafas = array [1..MAX_M, 1..MAX_M] of boolean;

  { ‘emiau apražyti globalieji kintamieji }
  var g: grafas; { pradinis grafas }
      n, m: integer; { lietuvi— bei japon— moksleivi— skai‡ius }
      K, D: lentele; { iežkomasis sprendinys; D[v] rodys numerŤ moksleivio,
                       kuris apgyvendins sve‡i… v }

  {--------------- Proced–ros darbui su eile ------------------------}
  procedure itraukti_i_eile (u: integer;  var Q:lentele;
                             var uodega: integer);
   { Ťtraukia Ť eil‚s pabaig… virž–nŠ u }
  begin
    Q[uodega] := u;
    uodega := uodega + 1;
  end; { Ťtraukti_Ť_eilŠ }

  procedure pasalinti_is_eiles (var galva: integer);
  begin
     galva := galva + 1
  end; { pažalinti_iž_eil‚s }

  {--------------- ­vedimo ir ižvedimo proced–ros ------------------------}
  procedure ivesti (var g: grafas; var n, m: integer);
  { Ťveda pradinius duomenis }
    var u, v, i, sk: integer;
        f: text;
  begin
    assign (f, PR);
    reset (f);
    readln (f, n, m); { su‘inomas lietuvi— ir japon— moksleivi— skai‡ius }
    { inicializuojamas grafas }
    for u := 1 to n do
      for v := 1 to m do
         g[u, v] := false;
    { sudaromas grafas }
    for u := 1 to n do
      begin
        read (f, sk);
        for i := 1 to sk do
          begin
            read (f, v);
            g[u, v] := true;
          end
      end;
    close (f)
  end; { Ťvesti }

  procedure isvesti (D: lentele);
    { ižvedami rezultatai }
    var f: text;
        v: integer;
  begin
    assign (f, RZ);
    rewrite (f);
    for v := 1 to m do
      writeln (f, D[v]);
    close (f);
  end; { ižvesti }

  {--------------- Rezultato suformavimas --------------------------------}
  procedure papildyti (liet: lentele; var japo: lentele);
   { kai daugiau pageidavim— patenkinti neŤmanoma, likŠ moksleiviai
     apgyvendimami neatsi‘velgiant Ť j— norus }
    var u, v: integer;
  begin
    u := 1;
    for v := 1 to m do
      if japo[v] = 0   { jei sve‡ias dar neapgyvendintas }
         then begin
                while liet[u] <> 0 do { iežkome sve‡io neturin‡io lietuvio }
                   u := u + 1;
                 japo[v] := u; liet[u] := v;  { apgyvendiname }
              end;
  end; { papildyti }

  {=============== Maksimalaus srauto paiežkos proced–ros ==========}
  procedure sprendinio_sudarymas (var K, D: lentele);
    { sudaro pirm… pasitaikiusŤ sprendinŤ }
    var u, v: integer;
  begin
    { inicializuojame graf… spr }
    for u := 1 to n do
      K[u] := 0;
    for v := 1 to m do
      D[v] := 0;
    { sudarome sprendinŤ }
    for u := 1 to n do
      begin
        v := 1;
        while (v <= m) and (K[u] = 0) do
          begin { kol nerasta pora arba neižnagrin‚ti visi variantai }
            if g[u, v] and (D[v] = 0)
               then begin
                      K[u] := v; D[v] := u;
                    end;
            v := v + 1;
          end;
      end;
  end; { sprendinio_sudarymas }

  {--------------------------- Naujo kelio paiežka-----------------------}
  procedure inicializuoti (var kel_K, ilgis: lentele;
                           var Q: lentele; var galva, uodega: integer);
   { inicializuojame kel_k ir eilŠ Q (Ť Q Ťtraukiamos laisvos virž–n‚s iž K)}
    var u: integer;
  begin
    { inicializuojamas kelias }
    for u := 1 to n do
      begin
        kel_K[u] := 0;
        ilgis[u] := maxint;
      end;
    { inicizlizuojama eil‚, Ť j… Ťtraukiamos laivos virž–n‚s iž K}
    galva := 1; uodega := 1;
    for u := 1 to n do
      if K[u] = 0
         then begin
                itraukti_i_eile (u, Q, uodega);
                ilgis[u] := 0;
              end;
  end; { inicializuoti }

  procedure ieskoti_kelio (var kel_K: lentele;   { rastasis kelias }
                           var pask_K, pask_D: integer;
                           { rastojo kelio pabaigos virž–n‚s }
                           var rasta: boolean);  { ar pavyko surasti keli… }
    { iežkomas kelias nuo bet kurios laisvos virž–n‚s iž K iki bet kurios
      laisvos virž–n‚s iž D }
    var ilgis,  { ilgis[u] - trumpiausio kelio iki u ilgis }
        Q: lentele; { eil‚ }
        galva, uodega: integer; { eil‚s prad‘ia ir pabaiga }
        u, v: integer;
  begin
    { inicializuojame kel_k ir eilŠ Q (Ť Q Ťtraukiamos laisvos virž–n‚s iž K)}
    inicializuoti (kel_k, ilgis, Q, galva, uodega);
    { vykdoma paiežka Ť plotŤ }
    rasta := false; { kelias dar nerastas }
    while (galva <> uodega) and not rasta do { kol eil‚ netuž‡ia }
      begin                                  { ir nerastas kelias }
        u := Q[galva]; { imamas pirmas eil‚s elementas }
        v := 1;
        while (v <= m) and not rasta do { iežkome lank— iž u Ť K virž–n‚s }
          begin
            if g[u, v] and ((D[v] = 0) or (ilgis[u]+2 < ilgis[D[v]]))
               { jei veda lankas iž u Ť v ir kelias trumpesnis nei
                 iki žiol rastasis arba prieita kelio pabaiga }
               then begin  { u-->v-->u' }
                      kel_K[D[v]] := u;           { iž u eisime Ť u'per v }
                      ilgis[D[v]] := ilgis[u]+2;  { atnaujiname ilgŤ iki u' }
                      itraukti_i_eile(D[v], Q, uodega);{ u' Ťtrauktas Ť eilŠ }
                      rasta := D[v] = 0;
                  end;
             v := v + 1
           end; { while (v <= m) and not rasta }
        pasalinti_is_eiles (galva);
      end;
    pask_K := u; pask_D := v-1;
  end; { iežkoti_kelio }
  {--------------------------- Naujo kelio paiežkos pabaiga ---------------}

  procedure atnaujinti_sprendini (var K, D: lentele; kel_K: lentele;
                                  u, v: integer);
    { suradus nauj… keli…, kurŤ nusako lentel‚s kel_K ir D,
      atnaujinamas sprendinys }
  begin
    repeat
      K[u] := v; D[v] := u;
      u := kel_K[u];
      v := K[u];
    until u = 0;
  end; { atnaujinti_sprendinŤ }


  procedure max_srautas (var K, D: lentele);
    { pagrindin‚ proced–ra, iežkanti maksimalaus srauto }
    var kel_K: lentele;    { kur ves naujas kelias iž aib‚s K virž–ni— }
        pask_K, pask_D: integer;  { dvi paskutin‚s kelio virž–n‚s }
        rasta: boolean;    { ar rastas naujas kelias }
  begin
    { sudarome bet kokŤ sprendinŤ }
    sprendinio_sudarymas (K, D);
    ieskoti_kelio (kel_K, pask_K, pask_D, rasta);
    while rasta do { kol pavyksta rasti keli… }
      begin
        { atnaujinamas sprendinys }
        atnaujinti_sprendini (K, D, kel_K, pask_K, pask_D);
        { iežkome naujo kelio }
        ieskoti_kelio (kel_K, pask_K, pask_D, rasta);
      end;
  end; { max_srautas }

  {======= Maksimalaus srauto paiežkos proced–r— pabaiga ===========}
{--------------- Pagrindin‚ programos dalis ------------------------}
begin
  ivesti (g, n, m);
  max_srautas (K, D);
  papildyti (K, D); { papildomas sprendinys }
  isvesti (D);
end.