1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <iostream>
#define maxn 100010
#define maxm 200010
#define INF 1000000000
using namespace std;
int n, m, q, t;
struct Edge {
int u, v, w;
} e[maxm];
namespace LCT {
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct LinkCutTree {
int v, val, ch[2];
bool rev;
} T[maxn + maxm]; int f[maxn + maxm];
void init() {
e[0].w = INF;
for (int i = 1; i <= m; ++i) T[i + n].val = i;
}
inline int get(int i) {
if (T[f[i]].ch[0] == i) return 0;
if (T[f[i]].ch[1] == i) return 1;
return -1;
}
inline void maintain(int i) {
T[i].v = T[i].val;
if (e[T[lc].v].w < e[T[i].v].w) T[i].v = T[lc].v;
if (e[T[rc].v].w < e[T[i].v].w) T[i].v = T[rc].v;
}
inline void setr(int i) {
if (!i) return ;
T[i].rev ^= 1; swap(lc, rc);
}
inline void push(int i) {
bool &rev = T[i].rev;
if (rev) setr(lc), setr(rc);
rev = 0;
}
inline void rotate(int x) {
int fa = f[x], ffa = f[f[x]], wx = get(x);
if (~get(fa)) T[ffa].ch[T[ffa].ch[1] == fa] = x;
f[x] = ffa; f[fa] = x; f[T[x].ch[wx ^ 1]] = fa;
T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
maintain(fa); maintain(x);
}
void clt(int i) {
static int st[maxn + maxm], top;
st[top = 1] = i;
while (~get(i)) st[++top] = i = f[i];
while (top) push(st[top--]);
}
void Splay(int i) {
clt(i);
for (int fa = f[i]; ~get(i); rotate(i), fa = f[i])
if (~get(fa)) rotate(get(i) == get(fa) ? fa : i);
}
void access(int i) { for (int p = 0; i; i = f[p = i]) Splay(i), rc = p, maintain(i); }
inline void make_rt(int i) { access(i); Splay(i); setr(i); }
inline void split(int x, int y) { make_rt(x); access(y); Splay(y); }
int find_rt(int i) { access(i); Splay(i); while (lc) i = lc; return Splay(i), i; }
inline void link(int x, int y) {
if (find_rt(x) == find_rt(y)) return ;
split(x, y); f[x] = y;
}
inline void cut(int x, int y) {
if (find_rt(x) != find_rt(y)) return ;
split(x, y);
if (T[y].ch[0] == x && !T[x].ch[1])
T[y].ch[0] = f[x] = 0, maintain(y);
}
}
namespace Seg {
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Zhuxi {
int v, ch[2];
} T[maxm * 100]; int rt[maxm], top;
void update(int &i, int j, int l, int r, int L, int R, int v) {
if (l > R || r < L) return;
i = ++top; T[i] = T[j];
if (L <= l && r <= R) return T[i].v += v, void();
int m = l + r >> 1;
update(lc, Lc, l, m, L, R, v); update(rc, Rc, m + 1, r, L, R, v);
}
int query(int i, int l, int r, int k) {
if (!i || l == r) return T[i].v;
int m = l + r >> 1;
if (k <= m) return query(lc, l, m, k) + T[i].v;
else return query(rc, m + 1, r, k) + T[i].v;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> q >> t;
for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v, e[i].w = i;
LCT::init();
for (int i = 1; i <= m; ++i) {
int u = e[i].u, v = e[i].v; Seg::rt[i] = Seg::rt[i - 1]; if (u == v) continue;
if (LCT::find_rt(u) == LCT::find_rt(v)) {
LCT::split(u, v); int k = LCT::T[v].v;
LCT::cut(e[k].u, k + n), LCT::cut(e[k].v, k + n);
Seg::update(Seg::rt[i], Seg::rt[i], 1, m, k + 1, i, 1);
} else Seg::update(Seg::rt[i], Seg::rt[i], 1, m, 1, i, 1);
LCT::link(u, i + n), LCT::link(v, i + n);
}
for (int i = 1, lans = 0; i <= q; ++i) {
int x, y; cin >> x >> y;
if (t) x = (x + lans) % m + 1, y = (y + lans) % m + 1;
if (x > y) swap(x, y);
cout << (lans = n - Seg::query(Seg::rt[y], 1, m, x)) << "\n";
}
return 0;
}
|