F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 3514. -- Codechef MARCH14 GERALD07加强版

3514: Codechef MARCH14 GERALD07加强版

Time Limit: 60 Sec  Memory Limit: 256 MB
Submit: 2790  Solved: 1092
[Submit][Status][Discuss]

Description

N个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数。

Input

第一行四个整数N、M、K、type,代表点数、边数、询问数以及询问是否加密。
接下来M行,代表图中的每条边。
接下来K行,每行两个整数L、R代表一组询问。对于type=0的测试点,读入的L和R即为询问的L、R;对于type=1的测试点,每组询问的L、R应为L xor lastans和R xor lastans。

Output

 K行每行一个整数代表该组询问的联通块个数。

Sample Input

3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2

Sample Output

2
1
3
1

HINT

对于100%的数据,1≤N、M、K≤200,000。


2016.2.26提高时限至60s

Source

By zhonghaoxi

[Submit][Status][Discuss]

HOME Back