Background

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.

Problem Description

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?

Input Format

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.

Output Format

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.

2
3 3
1 1
1 2
1 3
3 2
1 1
2 2

3
-1

Hint

[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