P5214 [SHOI2014] 神奇化合物

SHOI2014 day2t1

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

无

无

对于 30%的数据，$n, q\leq 1000$。 对于 100%的数据，$n\leq 5000,m\leq 200000,q\leq 10000$。