New update is available. Click here to update.

Posted: 1 Apr, 2021

Difficulty: Moderate

```
The range of elements in the ‘secondary’ sequence varies from 1 to N.
```

```
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.
```

```
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.
```

```
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.
```

```
1 <= T <= 10
1 <= N <= 10^5
1 <= primary[ i ] <= N
1 <= X, Y <= 10^3
Time Limit: 1 sec
```

Categories:

Popular Courses: