uses sysutils;

var
	i, j, k : integer;
	e : array[1..2000,1..2000] of boolean;
	cols : string;
	n, m : integer;
	u, v : integer;	
	
begin
	k := strtoint(paramstr(1));
	randseed := strtoint(paramstr(2));
	
	readln(n, m);
	readln(cols);
	for i := 1 to m do begin
		readln(u, v);
		e[u,v] := true;
		e[v,u] := true;
	end;
	
	for i := 1 to k do begin
		repeat
			u := random(n) + 1;
			v := random(n) + 1;
		until not e[u,v];
		e[u,v] := true;
		e[v,u] := true;
	end;

	writeln(n, ' ', m + k);
	writeln(cols);
	for i := 1 to n do
		for j := i + 1 to n do
			if e[i,j] then
				writeln(i, ' ', j);
end.
