# PART 2: VerifyOpt1() PROCEDURE:
# -----------------------

VerifyOpt1:=proc(n,G,B1,B2) local i,edge,v1,v2;
    for i from 1 to nops(G) do
        edge:=G[i];
        v1:=edge[1];
        v2:=edge[2];

        if B1[v1]<>B1[v2] then
            return false;
        elif B2[i]<>B1[v1] then
            return false;
        end if;
    od;

    return true;
end proc:

ZKP1:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
	sig:=randperm(n):
	for i from 1 to n do
		B1[i]:=sig[i]:
	od:

	for i from 1 to n do
		for j from i+1 to n do
			if member ({i,j},G) then
				B2[{sig[i],sig[j]}]:=1:
			else
				B2[{sig[i],sig[j]}]:=0:
			fi:
		od:
	od:

	if Opt=1 then
		return VerifyOpt1(n,G,B1,B2);
	else
		return evalb({seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}={1});
	fi:
end:

# PART 3: ZKP() PROCEDURE:
# -----------------------

ZKP:=proc(n,G,pi,K) local i, opt:
	for i from 1 to K do:
		opt = rand(1..2)();
		if ZKP1(n,G,pi,opt)=false:
			return false;
		fi;
	od;

	return true;
end;