P9343 A Cup of Wine for a New Song

Last night, I listened to songs at the pleasure house. With a pot of rough wine in hand, I looked at the bright moon by the railing. Thinking of my current situation, I did not feel lost. Instead, I was still fascinated by the joy of feasting and chanting verses. While raising my cup to the wind, I remembered a drinking-table game, and played it with my friends.

There are $n$ cups of wine on the table, numbered $1 \sim n$. Beside the table, there are many red paper slips with the character “wine” written on them. Next, these $n$ cups are operated on **in order** for $m$ operations. There are $2$ types of operations: - `1 x`: Put $1$ red slip on cup $x$. - `2 x`: Put $1$ red slip on each of the other $n-1$ cups, except cup $x$. Ask: after **at least** how many operations will every cup have at least one red slip?

**This problem has multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: - The first line contains two integers $n, m$. - The next $m$ lines each contain two integers $o_i, x_i$, representing the $i$-th operation.

For each test case: - If after $m$ operations there is still at least one cup without any red slip, output one line with `-1`. - Otherwise, output one line with an integer, the answer.

**[Sample 1 Explanation]** For the first test case: - After the $1$-st operation, cup $1$ has $1$ red slip, cup $2$ has $0$ red slips, and cup $3$ has $0$ red slips. - After the $2$-nd operation, cup $1$ has $1$ red slip, cup $2$ has $1$ red slip, and cup $3$ has $0$ red slips. - After the $3$-rd operation, cup $1$ has $1$ red slip, cup $2$ has $1$ red slip, and cup $3$ has $1$ red slip. **[Constraints and Notes]** **This problem uses bundled tests.** - Subtask 1 (20 points): $o_i = 1$. - Subtask 2 (20 points): $o_i = 2$. - Subtask 3 (20 points): all $x_i$ are equal. - Subtask 4 (20 points): $\sum n, \sum m \le 3 \times 10^3$. - Subtask 5 (20 points): no special restrictions. For $100\%$ of the data, $1 \le T, n, m, \sum n, \sum m \le 2 \times 10^5$, $o_i \in \{1, 2\}$, $1 \le x_i \le n$. Translated by ChatGPT 5