521

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

int n,d,s;
int BusStartAtStop[51];
int BusRunAtRoad[51];
int gr[31][31];
bool visit[51][51];
vector<int> vRoadstops[21];
vector<int> vBusRunAtRoad[21];

void init()
{
	for(int i=0;i<51;i++)
	{
		BusStartAtStop[i]=0;
		BusRunAtRoad[i]=0;
	}
	for(int i=0;i<31;i++)
		for(int j=0;j<31;j++)
			gr[i][j]=0;
	for(int i=0;i<21;i++)
	{
		vRoadstops[i].clear();
		vBusRunAtRoad[i].clear();
	}
}

void floydwarshall()
{
	for(int k=1;k<=d;k++)
	{
		for(int i=1;i<=d;i++)
		{
			for(int j=1;j<=d;j++)
			{
				gr[i][j] = gr[i][j] | (gr[i][k] & gr[k][j]);
			}
		}
	}
}


bool bfs(int bus1,int bus2)
{
	int stop1,stop2;
	int nxtStop1,nxtStop2;
	int root1=BusRunAtRoad[bus1],root2=BusRunAtRoad[bus2];
	queue<int> q;
	memset(visit,false,sizeof(visit));
	q.push(BusStartAtStop[bus1]);
	q.push(BusStartAtStop[bus2]);
	visit[BusStartAtStop[bus1]][BusStartAtStop[bus2]]=1;
	while(!q.empty())
	{
		stop1 = q.front();q.pop();
		stop2 = q.front();q.pop();
		if(stop1==stop2)
		return 1;
		for(int i=0;i<vRoadstops[root1].size();i++)
		{
			if(vRoadstops[root1][i]==stop1)
			{
				nxtStop1 = vRoadstops[root1][(i+1)%vRoadstops[root1].size()];
				break;
			}
		}
		for(int i=0;i<vRoadstops[root2].size();i++)
		{
			if(vRoadstops[root2][i]==stop2)
			{
				nxtStop2 = vRoadstops[root2][(i+1)%vRoadstops[root2].size()];
				break;
			}
		}
		if(!visit[nxtStop1][nxtStop2])
		{
			visit[nxtStop1][nxtStop2]=1;
			q.push(nxtStop1);
			q.push(nxtStop2);
		}
	}
	return 0;
}

int main()
{
	string st;
	int a,b;
	bool f;
	int val,start,bus,ret;
	stringstream ss;
	while(getline(cin,st))
	{
		ss.clear();
		ss<<st;
		ss>>n;
		ss>>d;
		ss>>s;
		if(n+d+s==0)
			break;
		init();
		for(int i=1;i<=n;i++)
		{
			ss.clear();
			getline(cin,st);
			ss<<st;
			while(ss>>val)
			{
				vRoadstops[i].push_back(val);
			}
			ss.clear();
			getline(cin,st);
			ss<<st;
			while(ss>>start>>bus)
			{
				BusStartAtStop[bus]=start;
				BusRunAtRoad[bus]=i;
				vBusRunAtRoad[i].push_back(bus);
			}
		}

		for(int i=1;i<=d;i++)
		{
			for(int j=i+1;j<=d;j++)
			{
				if(bfs(i,j)==1)
				gr[i][j]=1,gr[j][i]=1;
			}
			gr[i][i]=1;
		}
		floydwarshall();
		f =1;
		for(int i=1;i<=d;i++)
		{
			for(int j=1;j<=d;j++)
			{
				if(gr[i][j]==0)
				f=0;
			}
			if(f==0)
			break;
		}
		if(f)
		printf("Yes\n");
		else
		printf("No\n");
	}
	return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *