#LUOGUP8380. 一曲新词酒一杯

一曲新词酒一杯

题目背景

昨夜勾栏听曲,一壶浊酒,与明月凭栏相望,想起如今的处境,却没有怅然若失,仍然醉心于宴饮涵咏之乐,把酒临风之际,想起一种酒桌上的游戏,便和好友玩起来。

题目描述

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

接下来对这 nn 杯酒依次进行 mm 次操作。

操作共分为 22 种:

  • 1 x:给 xx 号酒贴上 11 张红纸。
  • 2 x:给除了 xx 号酒的其它 n1n-1 杯酒分别贴上 11 张红纸。

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

输入格式

本题有多组测试数据。

第一行一个整数 TT,表示测试数据组数。

对于每组测试数据:

  • 第一行两个整数 n,mn,m
  • mm 行每行两个整数 oi,xio_i,x_i,表示第 ii 次操作。

输出格式

对于每组测试数据:

  • 若在 mm 次操作后至少有一杯酒没有红纸,输出一行 -1
  • 否则输出一行一个整数表示答案。
2
3 3
1 1
1 2
1 3
3 2
1 1
2 2
3
-1

提示

【样例 1 解释】

对于第一组数据:

  • 11 次操作后,11 号酒有 11 张红纸,22 号酒有 00 张红纸,33 号酒有 00 张红纸。
  • 22 次操作后,11 号酒有 11 张红纸,22 号酒有 11 张红纸,33 号酒有 00 张红纸。
  • 33 次操作后,11 号酒有 11 张红纸,22 号酒有 11 张红纸,33 号酒有 11 张红纸。

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(20 points):oi=1o_i=1
  • Subtask 2(20 points):oi=2o_i=2
  • Subtask 3(20 points):所有 xix_i 均相等。
  • Subtask 4(20 points):n,m3×103\sum n,\sum m\le 3\times 10^3
  • Subtask 5(20 points):无特殊限制。

对于 100%100\% 的数据,1T,n,m,n,m2×1051\le T,n,m,\sum n,\sum m\le 2\times 10^5oi{1,2}o_i\in \{1,2\}1xin1\le x_i\le n