Description

A very long time ago, there were two countries living in harmony and without worries.

The annual evaluation begins. As two peaceful countries, the one with the largest friend circle is always the most respected. So now you need to find the maximum size of a friend circle. The two countries are denoted as A and B, and their descriptions are as follows:

• Country A: Each person has a friendliness value. For two people in Country A with friendliness values $a, b$, if $(a\mathbin{\mathrm{xor}} b) \bmod 2=1$, then the two people are friends; otherwise they are not.
• Country B: Each person has a friendliness value. For two people in Country B with friendliness values $a, b$, if $(a\mathbin{\mathrm{xor}} b) \bmod 2=0$ or $(a\mathbin{\mathrm{or}} b)$ has an odd number of $1$ bits in binary, then the two people are friends; otherwise they are not.

People between Countries A and B may also be friends. The testdata will provide the "friend" relations between A and B.

Friendship is bidirectional.

In Countries A and B, a friend circle is defined as follows: a set $S$, satisfying $S \subset A \cup B$, such that for all $i,j \in S$, $i$ and $j$ are friends.

Input Format

This problem contains multiple test cases.

• The first line contains an integer $T$, the number of test cases.
• For each test case:
  • Line 1 contains $3$ integers $A, B, M$, the number of people in Country A, the number of people in Country B, and the number of cross-country friend pairs, respectively.
  • Line 2 contains $A$ integers $a_i$, the friendliness values of the $i$-th person in Country A.
  • Line 3 contains $B$ integers $b_i$, the friendliness values of the $i$-th person in Country B.
  • Lines $4$ to $3+M$: each line contains two integers $x, y$, indicating that the $x$-th person in Country A and the $y$-th person in Country B are friends.

Output Format

Output $T$ lines, each containing an integer, the maximum size of a friend circle.

1
2 4 7
1 2
2 6 5 4
1 1
1 2
1 3
2 1
2 2
2 3
2 4

5

Hint

Sample Explanation

The maximum friend circle contains the $1$-st and $2$-nd people of Country A and the $1$-st, $2$-nd, and $3$-rd people of Country B.

Constraints

For $100\%$ of the testdata, $1 \le T \le 6$, $1 \le a_i, b_i < 2^{31}$.

There are two categories of testdata, and all test points satisfy at least one of the following:

• Category 1: $1 \le A \le 200$, $1 \le B \le 200$.
• Category 2: $1 \le A \le 10$, $1 \le B \le 3000$.

Translated by ChatGPT 5