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