Description

酒桌上共有 $n$ 杯酒，标号为 $1\sim n$。桌旁有许多写有“酒”字的红色纸片。

接下来对这 $n$ 杯酒依次进行 $m$ 次操作。

操作共分为 $2$ 种：

• 1 x：给 $x$ 号酒贴上 $1$ 张红纸。
• 2 x：给除了 $x$ 号酒的其它 $n-1$ 杯酒分别贴上 $1$ 张红纸。

问在至少几次操作后，每杯酒上至少有一张红纸？

Format

Input

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行两个整数 $n,m$。
• 后 $m$ 行每行两个整数 $o_i,x_i$，表示第 $i$ 次操作。

Output

对于每组测试数据：

• 若在 $m$ 次操作后至少有一杯酒没有红纸，输出一行 -1；
• 否则输出一行一个整数表示答案。

Samples

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

3
-1

【样例 1 解释】

对于第一组数据：

• 第 $1$ 次操作后，$1$ 号酒有 $1$ 张红纸，$2$ 号酒有 $0$ 张红纸，$3$ 号酒有 $0$ 张红纸。
• 第 $2$ 次操作后，$1$ 号酒有 $1$ 张红纸，$2$ 号酒有 $1$ 张红纸，$3$ 号酒有 $0$ 张红纸。
• 第 $3$ 次操作后，$1$ 号酒有 $1$ 张红纸，$2$ 号酒有 $1$ 张红纸，$3$ 号酒有 $1$ 张红纸。

Limitation

1s, 1024KiB for each test case. 对于 $100\%$ 的数据，$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$。