Bob and Indices

0

5 votes
Hashing Algorithm, String Algorithms, Algorithms
Problem

Bob is given three arrays \(A\), \(B\) and \(C\) of length \(N\) each. A pair of indices \((i,j)\), where \(0 \leq i, j \lt N\) is called good if \(A[i]\) is equal to \(B[C[j]]\).

Find an integer \(X\) denoting the number of good indices.

Input format

  • The first line contains an integer \(T\), which denotes the number of test cases.
  • The first line of each test case contains an integers \(N\), denoting the size of the array \(A\), \(B\) and \(C\).
  • The second line of each test case contains \(N\) space-separated integers, denoting the array \(A\).
  • The third line of each test case contains \(N\) space-separated integers, denoting the array \(B\).
  • The fourth line of each test case contains \(N\) space-separated integers, denoting the array \(C\).

Output format

For each test case, print an integer \(X\) denoting the number of good indices in a new line.

Constraints

\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 0 \leq A[i], B[i], C[i] \lt N\)

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case \(1\):

  • (0, 1) is a good pair as \(A[0] = B[C[1]]\).
  • (1, 2) is a good pair as \(A[1] = B[C[2]]\).
  • (1, 0) is a good pair as \(A[1] = B[C[0]]\).

Hence the answer is \(3\).

For test case \(2\)\(N\) is 1. So, only one good pair exists.

Editor Image

?