问题 22219 --NOI2014湖北省选二试第1题 神奇化合物

22219: NOI2014湖北省选二试第1题 神奇化合物

时间限制: 1 Sec  内存限制: 256 MB
提交: 41  解决: 8
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][8840kb]

题目描述

    科学家最近发现了一种高分子有机化合物SHTSC。这种物质的分子由单个或多个
  原子组成,原子之间通过化学键相互连接。SHTSC 十分不稳定,其原子之间的
  化学键经常会伴随着炫酷的声音特效和光影效果发生断裂或者重新连接。
    然而,令科学家们大为惊异的是,SHTSC 在变化过程中始终保持着一种特
  殊的性质:即不存在这样的原子序列a1,a2,…,an(n>3)满足a1 与a2、a2 与
  a3、……、an-1 与an 以及an 与a1 都通过化学键相连,但它们之间却没有其他
  化学键相连的情况。现在科学家将SHTSC 的原子由1 到n 标号,并告诉你
  SHTSC 的初始形态以及原子之间的化学键变化情况,他们想知道在实验过程中
  的某些时刻SHTSC 分裂成了多少个分子?

输入

    第一行两个整数:n, m。表示SHTSC 的总原子个数以及初始的化学键数。
    从第二行开始的m 行,每行两个整数a, b (1≤a,b≤n)。表示编号为a, b 的两
  个原子在初始状态中有化学键相连。数据保证每对a, b 只出现一次。
    第m+2 行有一个整数:q。表示实验的总操作数。
    之后q 行中的每一行为以下三种操作当中的一种:
    1、A i j 表示i 号原子与j 号原子之间形成了一条新的化学键;
    2、D i j 表示i 号原子与j 号原子之间原有的化学键断裂了;
    3、Q 询问当前SHTSC 分裂成了多少个不同的分子。

    数据保证所有的实验操作都是合法的。

【数据规模】
  对于30%的数据,n, q≤1000。
  对于100%的数据,n≤5000,m≤200000,q≤10000。

输出

  对于每个Q 操作,输出一行一个整数,为相应时刻的分子个数。

样例输入

7 10
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
2 5
10
Q
D 2 5
Q
D 5 6
D 5 7
Q
A 2 5
Q
A 5 6
Q

样例输出

1
2
3
2
1

提示

来源

[提交][状态]