Migrated from Lutece 2718 卷卷人的入侵

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

摆摆国正在遭到卷卷国的入侵！ 摆摆国总共有 $n$ 个重要城市，这些城市由 $m$ 条无向道路连接，即一个 $n$ 个点 $m$ 条边的图。 由于卷卷人不擅长攻城，所以卷卷人每次进攻会选择占据一些道路，分割并切断摆摆人的补给。 卷卷人会进行 $q$ 次进攻，每次占据除了道路编号在 $[l,r]$ 以外的所有道路，但是每次进攻后会在下一次进攻前放弃占领这些街道，即下次进攻前一瞬间所有道路都没有被占领。 为了有效抵御卷卷人的进攻，每次进攻后所有直接或间接联通（即能通过未被占领的边从一个走到另一个）的城市会组成一个联合体进行调度分配。为了掌握有效信息，摆摆人想知道每次进攻后有多少个联合体，即图中有多少个连通块。 但是由于摆摆人摆了，所以他们来向你求助。 有时摆摆人需要实时信息，所以会要求强制在线。

Input

第一行四个整数 $n,m,q,op$，分别表示点数、边数、进攻次数和是否强制在线。 接下来 $m$ 行每行两个空格隔开的整数 $u,v$ 表示一条连接 $u,v$ 两城市的道路 接下来 $q$ 行每行两个空格隔开的整数 $l,r$ 表示卷卷人的进攻。 如果 op=0，那么输入的 $l,r$ 即为真实的 $l,r$ 如果 op=1，那么真实的 $l,r$ 为 $l\bigoplus lastans,r\bigoplus lastans$，其中 $\bigoplus$ 表示异或运算，$lastans$ 表示上一次输出的答案，初始为 $0$。

Output

输出 $q$ 行整数表示每次进攻后连通块的个数

Samples

10 10 10 0
6 10
4 7
2 10
1 4
3 2
10 10
9 6
4 8
9 10
10 7
5 7
3 3
1 3
2 5
8 9
1 2
3 9
5 7
8 9
4 8

8
9
7
6
8
8
4
8
8
6

Constraints

$1\le n,m,k \le 2\times 10^5$ 保证真实的 $1\le l\le r\le m$

Resources

2022 UESTC ICPC Training for Data Structures