from bisect import * def scc(N,edges): M=len(edges) start=[0]*(N+1) elist=[0]*M for e in edges: start[e[0]+1]+=1 for i in range(1,N+1): start[i]+=start[i-1] counter=start[:] for e in edges: elist[counter[e[0]]]=e[1] counter[e[0]]+=1 visited=[] low=[0]*N Ord=[-1]*N ids=[0]*N NG=[0,0] def dfs(v): stack=[(v,-1,0),(v,-1,1)] while stack: v,bef,t=stack.pop() if t: if bef!=-1 and Ord[v]!=-1: low[bef]=min(low[bef],Ord[v]) stack.pop() continue low[v]=NG[0] Ord[v]=NG[0] NG[0]+=1 visited.append(v) for i in range(start[v],start[v+1]): to=elist[i] if Ord[to]==-1: stack.append((to,v,0)) stack.append((to,v,1)) else: low[v]=min(low[v],Ord[to]) else: if low[v]==Ord[v]: while(True): u=visited.pop() Ord[u]=N ids[u]=NG[1] if u==v: break NG[1]+=1 low[bef]=min(low[bef],low[v]) for i in range(N): if Ord[i]==-1: dfs(i) for i in range(N): ids[i]=NG[1]-1-ids[i] group_num=NG[1] counts=[0]*group_num for x in ids: counts[x]+=1 groups=[[] for i in range(group_num)] for i in range(N): groups[ids[i]].append(i) return groups N1,N2,N3,M=map(int,input().split()) NN=[N1+2,N2+2,N3+2] NNN=[0,N1+2,N1+N2+4,N1+N2+N3+6] K=N1+N2+N3 N=K+6 X=[] E=[(0,N1+2),(N1+2,N1+N2+4),(N1+1,N1+N2+3),(N1+N2+3,N1+N2+N3+5)] C=[] for i in range(N1+2): C.append(1) for i in range(N2+2): C.append(2) for i in range(N3+2): C.append(3) for i in range(4): E.append((E[i][1],E[i][0])) for i in range(N1+1): E.append((i+1,i)) for i in range(N2+1): i+=N1+2 E.append((i+1,i)) for i in range(N3+1): i+=N1+N2+4 E.append((i+1,i)) for i in range(M): u,v=map(int,input().split()) X.append((u,v)) u-=1 v-=1 if u=0 and T[I][i][3]>=0: v=T[I][i][1]-Y[0][0] w=T[I][i][3]-Y[1][0] Z[0][v]=(Z[0][v][0],1,w) Z[1][w]=(Z[1][w][0],0,v) ZZ[0][v]=i ZZ[1][w]=i elif T[I][i][1]>=0 and T[I][i][5]>=0: v=T[I][i][1]-Y[0][0] w=T[I][i][5]-Y[2][0] Z[0][v]=(Z[0][v][0],2,w) Z[2][w]=(Z[2][w][0],0,v) ZZ[0][v]=i ZZ[2][w]=i elif T[I][i][3]>=0 and T[I][i][5]>=0: v=T[I][i][3]-Y[1][0] w=T[I][i][5]-Y[2][0] Z[1][v]=(Z[1][v][0],2,w) Z[2][w]=(Z[2][w][0],1,v) ZZ[1][v]=i ZZ[2][w]=i for j in range(3): if T[I][i][j*2]0: if a>0: if a==Y[0][1]-Y[0][0]: a-=1 abc[0]-=1 W.append((a,b,c,0)) continue if not(Z[0][a][1]!=-1 and abc[Z[0][a][1]]>Z[0][a][2]): a-=1 abc[0]-=1 W.append((a,b,c,0)) continue if b>0: if b==Y[1][1]-Y[1][0]: b-=1 abc[1]-=1 W.append((a,b,c,1)) continue if not(Z[1][b][1]!=-1 and abc[Z[1][b][1]]>Z[1][b][2]): b-=1 abc[1]-=1 W.append((a,b,c,1)) continue c-=1 abc[2]-=1 W.append((a,b,c,2)) for i in range(len(W)): W[i]=list(W[i]) if ZZ[0][W[i][0]]==ZZ[1][W[i][1]]: W[i].append(0b10011001) elif ZZ[0][W[i][0]]==ZZ[2][W[i][2]]: W[i].append(0b10100101) elif ZZ[1][W[i][1]]==ZZ[2][W[i][2]]: W[i].append(0b11000011) else: W[i].append(0b11111111) W[i]=tuple(W[i]) dp=[[0]*8 for i in range(len(W))] dp[0][7]=1 for i in range(len(W)-1): for j in range(8): jj=j&(~(1<>W[i+1][3] for k in range(kk+1): jjj=jj|(k<>jjj)&1 and ((kk^k)==0 or Z[W[i+1][3]][W[i+1][W[i+1][3]]][0]==0): dp[i+1][jjj]+=dp[i][j] ANS+=sum(dp[-1]) print(ANS)