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$ | 无额外约束 |