Sequence Reconstruction

Given a sequence org of integers from 1 to n and a list of subsequences called seqs, determine whether org is the only shortest supersequence of all the given subsequences.

A supersequence is a sequence that contains each of the given subsequences as a subsequence. The shortest supersequence is one with the minimum possible length.

Return true if org is the only shortest supersequence of seqs, or false otherwise.

Examples

Example 1

Input: org = [1,2,3], seqs = [[1,2],[1,3]]

Output: false

Explanation: [1,2,3] is not the only shortest supersequence. [1,3,2] is also a valid shortest supersequence. Since the ordering is not unique, we return false.

Example 2

Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]

Output: true

Explanation: [1,2,3] is the only shortest supersequence of the given subsequences. Every pair of consecutive elements in org is constrained by the subsequences, making it the unique topological ordering.

Example 3

Input: org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]

Output: true

Explanation: The subsequences fully constrain the ordering so that [4,1,5,2,6,3] is the only valid shortest supersequence.

Constraints

• 1 <= n <= 10^4
• org is a permutation of integers from 1 to n
• 1 <= seqs.length <= 10^4
• 1 <= seqs[i].length <= 10^4
• 1 <= seqs[i][j] <= n