Colored cliques complexity

Question

Given:

1. graph with colored edges;

2. list of $\alpha$ colors;

3. list of $\epsilon$ colors;

4. clique size $k$.

Problem:

1. Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$?

2. Isn't there an edge of some of $\epsilon$ color that is not contained in clique of size $k$?

Example:

Given some graph that has blue, red, green and magenta edges.

$\alpha$ colors: red, blue.

$\epsilon$ colors: green, magenta.

Answer is yes if both conditions are satisfied:

1. All red and blue edges are contained in cliques of size $k$ (or larger, of course).

2. There exists at least one green and at least one magenta edges that are contained in some cliques of size $k$.

Here are 2 special cases, for both $n = 10, k = 4, \alpha$: red and blue, $\epsilon$ - green and magenta. The only difference is color of edge BE.

1st graph satisfies the conditions: all red and blue edges are contained in 4-vertex cliques ABIH, FGIJ, CDEF as well as they contain at least one green and at least one magenta edge.

2nd graph doesn't satisfy the conditions because blue edge BE is not a member of 4-vertex clique.

I think this problem is PSPACE-complete but I'm not sure about reduction from TQBF to this. If such reduction is possible, it is not similar to known SAT to max-clique reduction.