P10875 [COTS 2022] 游戏 M

译自 [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D2T2。$\texttt{3s,0.5G}$。

有一张 $N$ 个节点的无向图，依次向图中添加 $M$ 条边。 有 $Q$ 个询问，每次询问给定 $u,v$，问：至少添加前多少条边，才能使得 $u,v$ 间没有割边（换言之，割去任意一条边，都不影响 $u,v$ 的连通性）。特别地，如果 $u,v$ 始终不连通或者始终有割边，则输出 $-1$。

无

无

对于 $100\%$ 的数据，保证： - $2\le N \le 3\times 10^5$，$0\le M\le 3\times 10^5$，$1\le Q\le 3\times 10^5$； - $s_i\neq t_i$，$u\neq v$； - $1\le u,v,s_i,t_i\le N$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $10$ | $Q=1$ | | $2$ | $20$ | $2\mid M$，$(s_{2i-1},t_{2i-1})=(s_{2i},t_{2i})$ | | $3$ | $30$ | $N,M\le 5\, 000$ | | $4$ | $40$ | 无额外约束 |