Problem Brief

Effective Role Privileges

FULLTIMEPHONE SCREEN

See Snowflake online assessment and hiring insights

You are given n roles. Role i has a list of direct privileges privileges[i]. You are also given inheritance relations grants, where each pair [u, v] means role v inherits every privilege from role u.

The inheritance graph is a directed acyclic graph. A role's effective privileges are all privileges from its ancestors plus its own direct privileges.

Return the effective privileges for every role. Remove duplicates within each role and return each role's privilege list in lexicographic order.

1Example 1

Input

privileges = [["A"],["B"],["C"]], grants = [[0,1],[1,2]]

Output

[["A"],["A","B"],["A","B","C"]]

Explanation

Role 1 inherits role 0, and role 2 inherits both role 1 and role 0 transitively.

2Example 2

Input

privileges = [["READ"],["WRITE"],["DEPLOY"],["AUDIT"]], grants = [[0,2],[1,2],[2,3]]

Output

[["READ"],["WRITE"],["DEPLOY","READ","WRITE"],["AUDIT","DEPLOY","READ","WRITE"]]

3Example 3

Input

privileges = [["A","A"],["A"],[]], grants = [[0,1],[1,2]]

Output

[["A"],["A"],["A"]]

Constraints

Limits and guarantees your solution can rely on.

1 <= privileges.length <= 2 * 10^5
0 <= grants.length <= 2 * 10^5
Each grant is a pair [u, v] with 0 <= u, v < privileges.length.
The role inheritance graph is a DAG.
Privilege strings are non-empty tokens without spaces.