Determine feasibility and clean parentheses string

You are given two independent coding tasks.

1) Check if all courses/tasks can be completed

You have n courses labeled 0..n-1 and a list of prerequisite pairs prereq.

• Each pair [a, b] means: to take course a , you must finish course b first.
• Return true if it is possible to finish all n courses (i.e., there is no prerequisite cycle). Otherwise return false .

Input

• Integer n
• List of pairs prereq where each element is [a, b]

Output

• Boolean

Constraints (typical interview scale)

• 1 ≤ n ≤ 10^5
• 0 ≤ |prereq| ≤ 2*10^5

2) Remove the minimum invalid parentheses

Given a string s consisting of lowercase letters and parentheses '(' and ')', remove the minimum number of parentheses so that the resulting string is valid.

A string is valid if:

• Every ')' has a matching '(' before it.
• Parentheses are properly nested.

Return one valid string after performing the minimum removals.

Input

• String s

Output

• A valid string formed by deleting the minimum number of parentheses characters

Constraints (typical interview scale)

• 1 ≤ |s| ≤ 10^5

Notes

• Deleting letters is not allowed/needed; only delete parentheses.
• If multiple answers exist, returning any one is acceptable.