(*                              Maximum-Cardinality Matching Problem

        INPUT           : The associated datafile for Matching Algorithm is
                          "MatchDatafile".

                          1st number represents # of nodes in the given network\
 (N).
                          2nd set of numbers represents array of pointers in 
                                forward star form.
                          3rd set of numbers represents array of edges in 
                                forward-star form.

        OUTPUT  : Outputs are
                          1. MATE[1..N], indicates mathced nodes.
                          2. EXPO, number of exposed(unmatched) nodes
                          

        Algorithm       : The MATCH procedure is based on the Pape-Conradt
                          algorithm for finding a maximum-cardinality matching \
in
                          an undirected graph with no isolated nodes.
                          The input network in this algorithm is assumed to be \
in the 
                          forward-star form and has N nodes and M edges. 
                          The array POINTER points to the starting place in the\
 array
                          ENDV, whcih contains the list of adjacent nodes.  Sin\
ce
                          the given graph is undirected, every edge is represen\
ted 
                          twice- once from each end node.
                         The running time of this algorithm is O(n3) time in t\
he
                          worst case.
                                                                 *)


program Matching (input,output,MatchDatafile,MatchOutfile);

const 	maxvar = 50;
	maxarc2 = 50;


type	ARRM2 = array[1..maxarc2] of integer;
	ARRN = array[1..maxvar] of integer;
	ARRNB = array[1..maxvar] of boolean;
	ARRN1 = array[1..maxvar+1] of integer;
	CHARFILE = file of char;
        POINT = ^POINTLIST;
	POINTLIST = record
			R : POINT;
			L : POINT;
			ELEM : integer;
		    end;


var	N, M2 : integer;
	POINTER : ARRN1;
	ENDV : ARRM2;
	MATE : ARRN;
	EXPO : integer;
	MatchDatafile : CHARFILE;
	MatchOutfile  : CHARFILE;
	Nextint : integer;

procedure Infile (var N : integer;
		  var M2 : integer;
		  var POINTER : ARRN1;
		  var ENDV : ARRM2;
		  var Nextint : integer);

var counter : integer;

begin
  reset (MatchDatafile);
  readln (MatchDatafile,Nextint);
  N := Nextint;
  readln (MatchDatafile,Nextint);
  M2 := Nextint;
  for counter := 1 to N+1 do
  begin
    read (MatchDatafile,Nextint);
    POINTER[counter] := Nextint;
  end;
  readln (MatchDatafile);
  for counter := 1 to M2 do
  begin
    read (MatchDatafile,Nextint);
    ENDV[counter] := Nextint;
  end;
  readln(MatchDatafile);
end;




procedure MATCH(
       N          :integer;
   var POINTER    :ARRN1;
   var ENDV       :ARRM2;
   var MATE       :ARRN;
   var EXPO       :integer);

var	ADDTOTREE, FOUND	: boolean;
	GRANDFATHER, Q		: ARRN;
	HEAD, LAST, MATWI, NBHR, NEXT, ROOT,TAIL,VTX,X,Y : integer;
	NONTREE		: ARRNB;

procedure MAKEFIRSTMATCHING;

var LAST,X,Y : integer;

begin
    EXPO := N;
    for X := 1 to N do MATE[X] := 0;
    for X := 1 to N do
	if MATE[X] = 0 then
	  begin
	    Y := POINTER[X];
	    LAST := POINTER[X+1] -1;
	    while (MATE[ENDV[Y]] <> 0) and (Y < LAST) do
 		Y := Y + 1;
	    if MATE[ENDV[Y]] = 0 then
	    begin
		MATE[ENDV[Y]] := X;
		MATE[X] := ENDV[Y];
		EXPO := EXPO -2;
	    end;
          end;
end;

begin (* MATCH *)
  MAKEFIRSTMATCHING;
  for ROOT := 1 to N do
    if (EXPO >= 2) and (MATE[ROOT] = 0) then
    begin   (* Build tree only if root is an exposed node *)
      for X := 1 to N do NONTREE[X] := true;
      NONTREE[ROOT] := false;
      Q[1] := ROOT;
      HEAD := 1;
      TAIL := 1;
      FOUND := false;
      repeat
         VTX := Q[HEAD];
	 HEAD := HEAD + 1;
	 X := POINTER[VTX];
	 LAST := POINTER[VTX+1] -1;
	 while (not FOUND) and (X <= LAST) do
	 begin
	   if NONTREE[ENDV[X]] then
	   begin
	     NBHR := ENDV[X];
  	     MATWI := MATE[NBHR];
	     if MATWI = 0 then
	     begin
		MATE[NBHR] := VTX;
		repeat
		   NEXT := MATE[VTX];
     		   MATE[VTX] := NBHR;
		   if NEXT <> 0 then
		   begin
		      VTX := GRANDFATHER[VTX];
		      MATE[NEXT] := VTX;
		      NBHR := NEXT;
		   end;
                until NEXT = 0;
		EXPO := EXPO -2;
		FOUND := true;
             end 
             else if MATWI <> VTX then
	     begin
		if VTX = ROOT then ADDTOTREE := true
		else
		begin
		  Y := GRANDFATHER[VTX];
		  while (Y <> ROOT) and (Y <> NBHR) do
		    Y := GRANDFATHER[Y];
    		  if Y = ROOT then ADDTOTREE := true
                  else  ADDTOTREE := false;
		end;
		if ADDTOTREE then
		begin
		  NONTREE[NBHR] := false;
		  GRANDFATHER[MATWI] := VTX;
		  TAIL := TAIL+ 1;
		  Q[TAIL] := MATWI;
		end;
	     end;
         end; (* if *)
         X := X+1;
       end; (* while *)
     until FOUND or (HEAD > TAIL)
   end; (* if *)
end;   (* MATCH *)  



procedure Outfile (MATE : ARRN;
		   EXPO : integer);

var counter : integer;

begin
  rewrite(MatchOutfile);
  writeln (MatchOutfile,' The solution obtained using Matching Algorithm is ');
  for counter := 1 to N do
  begin
    write (MatchOutfile,'MATE',counter,'    and');
    writeln (MatchOutfile,MATE[counter]);
  end;
  writeln(MatchOutfile);
  writeln(MatchOutfile);
  write (MatchOutfile,'Number of unmatched nodes is -> ',EXPO);
  writeln(MatchOutfile);
end;


begin
  Infile (N,M2,POINTER,ENDV,Nextint);
  MATCH (N,POINTER,ENDV,MATE,EXPO);
  Outfile (MATE,EXPO);
end.