由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，色括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍(n不超过3000)，每个间谍分别用1到3000的整数来标识。

请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

输入文件age.in第一行只有一个整数n。

第二行是整数p。表示愿意被收买的人数，1≤p≤n。

接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。

紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间谍掌握B间谍的证据。

如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#define maxn 3010

using namespace std;

int n,i,j,k,l,m,p,co,tim,top,t,ans;

struct st{int nex,to;}mu[maxn*6];

int s[maxn],last[maxn],bcc[maxn],bo[maxn],pre[maxn],low[maxn],b[maxn],xx[maxn*3],yy[maxn*3];

int dfs(int u)

{

	pre[u]=low[u]=++tim;

	int v;s[++top]=u;

	for(int z=last[u];z;z=mu[z].nex)

	{

		v=mu[z].to;

		if(!pre[v])

		{

			dfs(v);

			low[u]=min(low[u],low[v]);

		}

		else if(!b[maxn])

		low[u]=min(low[u],pre[v]);

	}

	if(pre[u]==low[u])

	{

		++co;

		for(; ;)

		{

			b[s[top]]=1;

			bcc[s[top--]]=co;

			if(s[top+1]==u)break;

		}

	}

}

void add(int x,int y)

{

	t++;mu[t].nex=last[x];

	mu[t].to=y;last[x]=t;

}

int main()

{

//	freopen("xx.in","r",stdin);

	scanf("%d%d",&n,&p);

	for(i=1;i<=p;++i)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		bo[u]=v+1;

	}

	scanf("%d",&m);

	for(i=1;i<=m;++i)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		add(u,v);

		xx[i]=u;yy[i]=v;

	}

	for(i=1;i<=n;++i)

	if(!pre[i])

	{

		top=tim=0;

		dfs(i);

	}

	for(i=1;i<=co;low[i]=1e9,++i)s[i]=b[i]=0;

	for(i=1;i<=m;++i)

	{

		if(bcc[xx[i]]==bcc[yy[i]])continue;

		s[bcc[yy[i]]]=1;

	}

	for(i=1;i<=n;++i)

	if(bo[i])

		low[bcc[i]]=min(low[bcc[i]],bo[i]-1);

	for(i=1;i<=co;++i)

	if(!s[i])

	{

		if(low[i]==1e9)

		{

			for(j=1;j<=n;++j)

			if(bcc[j]==i)break;

			printf("NO\n%d",j);

			return 0;

		}

		ans+=low[i];

	}

	printf("YES\n%d",ans);

}

Freda是一个迷宫爱好者，她利用业余时间建造了许多迷宫。每个迷宫都是由若干房间和走廊构成的，每条走廊都连接着两个不同的房间，两个房间之间最多只有一条走廊直接相连，走廊都是双向通过。

黄昏时候，Freda喜欢在迷宫当中漫步。每天，Resodo都会为Freda设计一个挑战方案。Resodo会指定起点和终点，请Freda来找到一条从起点到终点的简单路径。一条简单路径定义为一个房间序列，每个房间至多在序列里出现一次，且序列中相邻的两个房间有走廊相连。当起点和终点之间存在且仅存在一条简单路径的时候，Freda认为这个挑战方案是RD的。现在，请你帮帮Resodo来写一个程序，判断一个挑战方案是否是RD的。

第一行三个整数N,M,Q.分别表示房间数，走廊数，询问数。

接下来M行每行2个整数x,y, 0<=N, 表示x和y之间有一条走廊相连。

接下来Q行每行2个整数x,y, 表示询问以x为起点,y为终点的挑战方案是否是RD的.

对于每个询问，输出一行”Y”或者”N”（不含引号）.Y表示该询问所表示的挑战方案是RD的,N表示该询问所表示的挑战方案不是RD的.

样例解释

1,3之间只有一条路径 1->2->3

1,5之间有两条路径 1->2->5 ; 1->2->4->5

1,6之间没有路径

数据范围与约定

对于30%的数据，N<=100， M<=1000, Q<=100.

对于50%的数据，N<=1000, M<=10000, Q<=1000.

对于100%的数据，N<=10000, M<=100000, Q<=10000.

按题意在线处理定会超时；

怎么做到离线算法？

首先有简单路径必须保证两点联通 且只有唯一路径；

那么这条路径一定由桥组成；那就可以保证路径唯一，且联通；

用Tarjan求桥；

将桥两端点归进一个集合 这时就要用到并查集了；

最后对于每个询问只要判断两点在同一集合就能保证有唯一路径；

#include<cstdio>

#include<iostream>

#define maxn 10010

using namespace std;

int n,t,i,j,k,l,m,q,tim,_bcc,_scc,top,fu,fv;

int last[maxn],bcc[maxn],scc[maxn],pre[maxn],low[maxn],f[maxn];

struct st{int nex,to;}mu[maxn*20];

void add(int x,int y)

{

	t++;mu[t].nex=last[x];

	mu[t].to=y;last[x]=t;

}

int gets(int x)

{return f[x]==x ? x:f[x]=gets(f[x]);}

int dfs(int u,int fa)

{

	pre[u]=low[u]=++tim;

	int v;

	for(int z=last[u];z;z=mu[z].nex)

	{

		v=mu[z].to;

		if(!pre[v])

		{

			dfs(v,u);

			low[u]=min(low[u],low[v]);

			if(pre[u]<low[v])

			{

				fu=gets(u);fv=gets(v);

				if(fu!=fv)f[fv]=fu;

			}

		}

		else if(pre[u]>pre[v]&v!=fa)

				low[u]=min(pre[v],low[u]);

	}

	return low[u];

}

int main()

{

//	freopen("xx.in","r",stdin);

	scanf("%d%d%d",&n,&m,&q);

	for(i=1;i<=m;++i)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		add(u,v);add(v,u);

	}

	for(i=1;i<=n;++i)f[i]=i;

	for(i=1;i<=n;++i)

	if(!pre[i])

	{

		tim=0;top=0;

		dfs(i,-1);

	}

	for(i=1;i<=q;++i)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		u=gets(u);v=gets(v);

		if(u==v)printf("Y\n");

		else printf("N\n");

	}

}