Description

亚特兰蒂斯人激怒了众神，众神之王宙斯决定要好好教化他们。这时，一位居心叵测的bug魔王看准了时机，打着“教化亚特兰蒂斯人”的旗号，暗地里策划了一个极具野心的阴谋：铲平亚特兰蒂斯。善良的宙斯并没有发现他的阴谋，草率地批准了他这次“教化”行动，于是一场危机就要降临亚特兰蒂斯了。。。

幸好亚特兰蒂斯拥有一位相当优秀的先知Cubic，他发现了bug魔王的阴谋，并了解到bug魔王会派出N种怪物来入侵亚特兰蒂斯，现在就要想办法对付这N种怪物。Cubic还了解到，每一种怪物都对应一种剑术和一种法术，这种怪物可以被这对应的剑术打败，也可以被对应的法术打败。不同的怪物可能对应不同的剑术和法术，而一种剑术或法术可以击败多种怪物。只要Cubic得到某怪物的信息，他就可以知道对应的剑术和法术，不会只知其一。

亚特兰蒂斯里最优秀的剑术师是RC，最优秀的法术师是Aesop，这次为了保护亚特兰蒂斯，他们都愿意挺身而出。但问题是他们并不会这些特定的剑术和法术，必须抓紧时间学习。但由于学习新剑术或新法术需要闭关学习，为了避免bug魔王搞奇袭，必须至少留下其中一个专门看守，于是他们两个就不能同时去学习了。

现在bug魔王已经屯好兵了，时间所剩无几，他们必须在最短的时间内学会相应的剑术和法术，以打败所有的怪物。学习一种剑术或一种法术所需要的时间都为1。现在问题是，他们到底应该学习哪种剑术和法术，才能在最短时间内拥有打败所有怪物的能力呢？

即便是再聪明的Cubic这次都头痛了。于是他找到了你——亚特兰蒂斯的顶级技术顾问，来帮他解决这个问题。所以，拯救亚特兰蒂斯的重任就交给你了。

Input

输入有多组数据。对于每组数据：
第1行是3个整数P(1<=P<=10000),N(0<=N<=500)和M(0<=M<=500)，分别表示怪物种数、剑术种数和法术种数，它们之间分别用一个空格隔开。

接下来有P行，每行一个字符串，分别表示这P种怪物的名字。

再接下来有N+M行，表示一种剑术或法术的信息。前N行是剑术，后M行是法术。对于每一行，首先是一个字符串，表示剑术或法术的名字；然后是一个非负整数K(K<=P)，表示这种剑术或法术可以击败的怪物种数；然后就是K个字符串，表示这K种怪物。这些怪物都在上面的P种之内。

所有的字符串都只由字母和连字符（-）组成，长度不超过15。两个字符串以空格隔开。所有的字符串都不相同。最后一行有3个-1，表示输入结束。

Output

对于每组数据，输出一个整数，表示要拥有打败所有怪物的能力所需要的最少的时间。如果无法打败所有的怪物，输出“Poor Atlantis!”。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 3 2
ant
rocking
kinfkong
savior
magicpig
AloneNineSword 2 ant kinfkong
HuashanSword 2 rocking savior
TaijiSword 1 magicpig
Wind-walk 3 ant rocking magicpig
Blade-storm 2 kinfkong savior
-1 -1 -1

Sample Output

1
2

Solution

唔，我们可以知道，一个怪兽只对应着一种剑术和一种法术（大力吐槽怪兽的名字魔法猪）（大数据的怪兽名可以说非常不走心monster114）。

所以说我们假如把剑术放在左边，法术放在右边，以怪兽为边，就可以构造出一个二分图。

此时我们要求的是这个二分图的最小点覆盖

设怪兽边的容量为∞\infin，源点到每一种剑术的边容量为11，每一种法术到汇点的边容量为11

跑一遍最大流DinicDinic即可

最大流量就是答案

我们可以发现，这些怪兽的名字，剑术的名字和法术的名字没有什么实际意义，所以你可以只用他们的idid就可以了，例如在剑术的时候用一个map来存小怪的名字和idid，在法术的时候取出来

还有无解的情况：先知Cubic知道怪兽的克星不会只知其一，但是有可能他什么都不知道

那你就无法使用任何法术或者剑术来攻击一个没有克星的怪兽

代码

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
#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#define N 1005
#define inf 10000000000
using namespace std;
map<string,int> h;
struct Edge{long long u,v,c,f;};
vector<Edge> e;
vector<int> g[N];
long long d[N],cur[N];
bool vis[N];
int n,m,s,t,p,sum;
void init()
{
	for (long long i=0;i<=n+m+1;++i)
		g[i].clear();
	e.clear();
}
void addEdge(long long u,long long v,long long c)
{
	e.push_back(Edge{u,v,c,0});
	e.push_back(Edge{v,u,0,0});
	long long s=e.size();
	g[u].push_back(s-2);
	g[v].push_back(s-1);
}
bool bfs()
{
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(s),d[s]=1,vis[s]=1;
	while (!q.empty()) {
		long long i=q.front();q.pop();
		for (long long j=0;j<(int)g[i].size();++j) {
			Edge k=e[g[i][j]];
			if (!vis[k.v]&&k.c>k.f)
				d[k.v]=d[i]+1,vis[k.v]=1,
					q.push(k.v);
		}
	}return vis[t];
}
long long dfs(long long x,long long a)
{
	if (x==t || a==0) return a;
	long long flow=0,f;
	for (long long& i=cur[x];i<(int)g[x].size();++i)
	{
		Edge& k=e[g[x][i]];
		if (d[x]+1!=d[k.v]) continue;
		f=dfs(k.v,min(a,k.c-k.f));
		if (f<=0) continue;
		k.f+=f,flow+=f,a-=f,
		e[g[x][i]^1].f-=f;
		if (a==0) break;
	}return flow;
}
long long dinic()
{
	long long flow=0; while (bfs())
		memset(cur,0,sizeof(cur)),
			flow+=dfs(s,inf);
	return flow;
}
int main()
{
	while (1)
	{
		scanf("%d%d%d",&p,&n,&m);
		if (p==-1&&n==-1&&m==-1) break;
		s=0,t=n+m+1;init();sum=0;
		for (int i=1;i<=p;++i) {
			char s[20];
			scanf("%s",s);
		}for (int i=1,k;i<=n;++i)
		{
			char s[20];
			scanf("%s%d",s,&k);
			sum+=k;
			addEdge(0,i,1);
			for (int j=1;j<=k;++j)
				scanf("%s",s),h[s]=i;
		}
		for (int i=n+1,k;i<=n+m;++i)
		{
			char s[20];
			scanf("%s%d",s,&k);
			addEdge(i,t,1);
			for (int j=1;j<=k;++j)
				scanf("%s",s),
				addEdge(h[s],i,inf);
		}if (sum<p) {
			puts("Poor Atlantis!");
			continue;
		}long long ans=dinic();
		if (ans) printf("%lld\n",ans);
		else puts("Poor Atlantis!");
	}
}