New update is available. Click here to update.

# Sequence Reconstruction

Posted: 1 Apr, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### The shortest common supersequence of two sequences, ‘A’ and ‘B’, is the shortest sequence such that ‘A’ and ‘B’ are subsequences of it.

##### Note :
``````The range of elements in the ‘secondary’ sequence varies from 1 to N.
``````
##### For Example :
``````If primary = [ 1, 2, 3 ] and secondary = [ [ 1, 2 ], [ 1, 3 ] ]
[ 1, 2, 3 ] is shortest common supersequence of [ 1, 2 ] and [ 1, 3 ]. But [ 1, 3, 2 ] is also a shortest common super sequence of [ 1, 2 ] and [ 1, 3 ]. As [ 1, 2, 3 ] is not the only shortest supersequence, you need to return false.
``````
##### Input Format :
``````The first line contains ‘ T ‘, denoting the number of test cases.

The first line of each test case contains three space-separated integers, N - number of elements in ‘primary’ sequence, ‘ X ‘ - number of sequences in ‘secondary’ sequence, and ‘ Y ‘ - number of elements in each sequence of ‘secondary’ sequence.

Each test case’s second line contains ‘ N ’ space-separated integers denoting elements of the ‘primary’ sequence.

The following ‘ X ‘ lines of each test case contain ‘ Y ‘ space-separated integers.
``````
##### Output Format :
``````For each test case, return “ True “ if ‘primary’ is the only shortest supersequence of all the sequences in the ‘secondary’ sequence. Otherwise, return “ False “.

Print the output of each test case in a separate line.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N <= 10^5
1 <= primary[ i ] <= N
1 <= X, Y <= 10^3

Time Limit: 1 sec
``````