Help:=proc(): print(`RG3C(n), ZKP3(n,G,C,Opt),   Verify1(n,G,B1v,B2), Verify2(n,G,B1c,S)`): end:
with(combinat):



RG3C:=proc(n) local ra,i,j,C,ra1,G:
ra:=rand(1..3):
C:=[seq(ra(),i=1..n)]:
ra1:=rand(0..1):
 G:={}:
for i from 1 to n do
 for j from i+1 to n do
   if C[i]<>C[j] then
    if ra1()=1 then
      G:=G union {{i,j}}:
    fi:
   fi:
 od:
od:
n,G,C:
end:


ZKP3:=proc(n,G,C,Opt) local c,L,i,j,sig,BiV,BiC,BjV,BjC,B1,B1c,B1v,B2,S:
#box is a pair [color,vertex]
L:=[seq(seq([c,i],i=1..n),c=1..3)]:
sig:=randperm(3*n):
B1:=[seq(L[sig[i]],i=1..3*n)]:

for i from 1 to 3*n do
  for j from 1 to 3*n do
    BiV:=B1[i][2]:
    BiC:=B1[i][1]:
    BjV:=B1[j][2]:
    BjC:=B1[j][1]:
   if C[BiV]=BiC and C[BjV]=BjC and member({BiV,BjV},G) then
     B2[i,j]:=1:
    else
     B2[i,j]:=0:
   fi:
 od:
od:
B2:=[seq([seq(B2[i,j],j=1..3*n)],i=1..3*n)]:


if Opt=1 then
  B1v:=[seq(B1[i][2],i=1..nops(B1))]:
    Verify1(n,G,B1v,B2):

else
B1c:=[seq(B1[i][1],i=1..nops(B1))]:
 S:={}:
 for i from 1 to 3*n do
   for j from i+1 to 3*n do
    if B1[i][1]=B1[j][1] then
       S:=S union {[[i,j],B2[i][j]]}:
    fi:
   od:
od:
Verify2(B1c,S):
fi:
end:


#Verify1(n,G,B2,B1v): inputs a graph n,G, a 3*n by 3*n 0-1 matrix B2 and the vertex-part of B1 (a list of length 3*n) checks whether the prover had
#a honest description of the graph
Verify1:=proc(n,G,B1v,B2) local i,j:

for i from 1 to 3*n do
for j from i+1 to 3*n do
  if not member({B1v[i],B1v[j]},G) and B2[i][j]=1 then
   print(`Liar!`):
   RETURN(false):
 fi:
od:
od:
true:
end:



#Verify2(B1c,S)
Verify2:=proc(B1c,S) local s:
for s in S do
 if s[2]<>0 then
  print(`Liar! `):
  RETURN(false):
 fi:

 if B1c[s[1][1]]<>B1c[s[1][2]] then
   print(`Liar! `):
  RETURN(false):
 fi:
od:
true:
end: