Maximum Friendship Clique

In ancient times, two nations A and B lived in harmony. Every year, a grand contest was held to determine which nation had the most expansive circle of friends. In these two countries, each person is assigned a friendly value. The friendship relation is defined as follows:

Within Country A:

• For any two persons with friendly values a and b, they are friends if \[ (a \oplus b) \bmod 2 = 1, \] otherwise, they are not friends. (Here \(\oplus\) denotes the bitwise XOR operation.)

Within Country B:

• For any two persons with friendly values a and b, they are friends if either \[ (a \oplus b) \bmod 2 = 0 \] or \[ \text{popcount}(a \mathbin{|} b) \text{ is odd}, \] where \(a \mathbin{|} b\) denotes the bitwise OR of a and b and \(\text{popcount}(x)\) counts the number of 1's in the binary representation of \(x\).

Between Countries A and B:

• The friendship relationships between people of country A and country B are provided explicitly in the input.

A friend circle (or clique) in this problem is defined as a subset \(S \subset A \cup B\) such that every pair of persons \(i, j \in S\) are friends (i.e. the friendship relation is bidirectional and holds for every pair in \(S\)).

Your task is to determine the maximum size of a friend circle.

inputFormat

The input begins with two integers \(n\) and \(m\) representing the number of people in country A and country B, respectively.

The second line contains \(n\) integers, representing the friendly values of the people in country A.

The third line contains \(m\) integers, representing the friendly values of the people in country B.

The fourth line contains a single integer \(k\), the number of explicit friendship relations between people of country A and country B.

Each of the following \(k\) lines contains two integers \(i\) and \(j\) (1-indexed), indicating that the \(i\)th person in country A and the \(j\)th person in country B are friends.

outputFormat

Output a single integer: the size of the largest friend circle (clique) such that every two persons in the circle are friends.

sample

2 2
1 2
3 4
1
1 2

2