← 返回题目列表

Codeforces · 398/D

D. 即时通讯工具

中文机器翻译题面 查看原题

用户 ainta 决定制作一个名为“aintalk”的新即时通讯工具。通过 aintalk,每个用户都可以与其他人聊天。用户ainta做了一些功能的原型来实现这个东西。

1.登录(u):用户u登录aintalk并上线。
2.注销(u):用户u注销并离线。
3. add_friend(u, v):用户u和用户v成为好友。这意味着,u 和 v 可以互相通话。友谊是双向的。
4. del_friend(u, v):取消用户u和用户v的好友关系。这意味着,从此以后u和v不能互相交谈。
5. count_online_friends(u):该函数返回用户u当前在线的好友数量。

由于该Messenger正在由编号为1到n的一些用户进行测试,因此没有注册方法。这意味着,一开始,有些用户可能在线,有些用户可能有朋友。

用户 ainta 打算实现这些功能,但在公开该功能之前,他想知道自己的想法是否正确。帮助 ainta 验证他的代码。

输入

第一行包含三个空格分隔的整数 n、m 和 q (1 ≤ n ≤ 50000; 1 ≤ m ≤ 150000; 1 ≤ q ≤ 250000) — 用户数、好友对数和查询数。

第二行包含一个整数o(1≤o≤n)——开头的在线用户数。第三行包含 o 个空格分隔的整数 x1, x2, ..., xo (1 ≤ xi ≤ n) — 在线用户的 id。保证这些值是不同的。

接下来的 m 行中的每一行都包含两个以空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 最初是朋友的两个用户的 id。保证输入中没有给出多重友谊。请注意,友谊是双向的。

接下来 q 行描述 q 查询,格式如下:

- "O u" (1 ≤ u ≤ n) : 在线呼叫(u)。保证用户 u 在函数调用之前处于离线状态。
- "Fu" (1 ≤ u ≤ n) : 呼叫离线(u)。保证用户 u 在函数调用之前在线。
- "A u v" (1 ≤ u, v ≤ n; u ≠ v) :调用 add_friend(u, v)。可以保证这两个用户在函数调用之前不是朋友。
- "D u v" (1 ≤ u, v ≤ n; u ≠ v) :调用 del_friend(u, v)。保证这两个用户在函数调用之前是朋友。
- "C u" (1 ≤ u ≤ n) :调用 count_online_friends(u) 并在一行中打印结果。

输出

对于每个 count_online_friends(u) 查询,在一行中打印所需的答案。

示例

输入 #1

5 2 9
1
4
1 3
3 4
C 3
A 2 5
O 1
D 1 3
A 1 2
A 4 2
C 2
F 4
C 2

输出 #1

1
2
1