题目描述

给定 $m$ 个区间，求长为 $2n$ 的字典序最小的合法括号串，满足每个区间内至少有一个左括号。若无解，则输出 -1。

我们规定左括号的字典序小于右括号。

输入格式

本题包含多组测试数据，第一行包含一个整数 $T$ ($1 \leq T \leq 10^5$)，代表测试数据数量。

对于每组输入数据，第一行先输入两个正整数 $n, m(1 \leq n, m \leq 10^5)$，分别表示需要构造的括号串的长度的一半，以及限制区间的个数。

接下来 $m$ 行，每行两个正整数 $l, r(1 \leq l \leq r \leq 2 \cdot n)$，表示构造的括号串需要满足 $[l, r]$ 中至少有一个左括号。

保证 $\sum n \leq 2 \cdot 10^5$，且 $\sum m \leq 4 \cdot 10^5$。

输出格式

对于每组输入数据，输出一个字符串，表示构造的字典序最小的合法括号串。若无解，输出 -1。

3
2 2
1 2
3 4
3 4
1 1
2 2
3 3
4 4
5 3
2 4
3 9
7 10

()()
-1
(((())()))