uses sysutils;

const
	max_n = 2000;
	max_m = 30000;
	
var
	p, ip : array[1..max_n] of integer;
	used : array[1..max_m] of boolean;
	ep : array[1..max_m] of integer;
	
	n, m : integer;
	i, j : integer;
	cols : string;
	u, v : array[1..max_m] of integer;
	
begin
	randseed := strtoint(paramstr(1));
	
    readln(n, m);
    writeln(n, ' ', m);
    readln(cols);
    for i := 1 to m do
    	readln(u[i], v[i]);
    
    fillchar(used, sizeof(used), false);
    for i := 1 to n do begin
    	repeat
    		j := random(n) + 1;
    	until not used[j];
    	p[i] := j;
    	ip[j] := i;
    	used[j] := true;	
    end;

    fillchar(used, sizeof(used), false);
    for i := 1 to m do begin
    	repeat
    		j := random(m) + 1;
    	until not used[j];
    	ep[i] := j;
    	used[j] := true;	
    end;

    for i := 1 to n do
    	write(cols[ip[i]]);
    writeln;
    	    
    for i := 1 to m do
    	writeln(p[u[ep[i]]], ' ', p[v[ep[i]]]);
end.
