Propagate allow/disallow labels on a DAG and compute effective allowed set per node

Problem: Propagate allow/disallow labels on a DAG and compute effective allowed set per node You are given a directed acyclic graph (DAG) G(V, E). Each node v has two sets of lowercase letters: Allow(v): allowed letters Disallow(v): disallowed letters The rule is transitive along paths: if there is a path from u to v, then u's allow/disallow constraints affect v. For each node v, define the accumulated sets from all ancestors (including itself): A(v) = ⋃ Allow(x) over all ancestors x of v (including v) D(v) = ⋃ Disallow(x) over all ancestors x of v (including v) The effective allowed set at node v is: Effective(v) = A(v) \ D(v) Input Format First line: integers n m (#nodes, #edges) Next n lines: two strings allow_i disallow_i (lowercase a-z, - means empty) Next m lines: edges u v meaning u -> v (1-indexed), guaranteed acyclic Output Format Print n lines. Line i is Effective(i) in sorted order, or - if empty. Constraints 1 ≤ n ≤ 2e5 0 ≤ m ≤ 2e5 Alphabet size is fixed to 26. Examples See the tests field below. Example Input 3 2 a - - b c - 1 2 2 3 Output a a ac