1 /*
2 树形dp!
3 判重思路:
4 当dp[v][0]==dp[v][1]时,很自然,flag[u][0]必然是有两种方案的。flag[u][1]则不然,
5 因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时,则必然flag[u][1]也不唯一
6 也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样),那么父节点u不选的时候一定会有
7 多种方案!也就是flag[u][0]=false; 否则如果flag[v][0]==flase(子节点不选的时候有多种方案),
8 那么父节点u选择的时候一定有多种方案,则flag[u][1]=false;
9 */
10 #include<iostream>
11 #include<cstring>
12 #include<cstdio>
13 #include<string>
14 #include<map>
15 #include<algorithm>
16 #define N 205
17 using namespace std;
18
19 map<string, int>mp;
20 int n;
21 int cnt;
22 int g[N][N];
23 int dp[N][2];
24 bool flag[N][2];
25 map<string, int>::iterator it;
26
27 void dfs(int u){
28 for(int v=1; v<=n; ++v)
29 if(g[u][v]){
30 dfs(v);
31 dp[u][1]+=dp[v][0];
32 dp[u][0]+=max(dp[v][1], dp[v][0]);
33 if(dp[v][1]==dp[v][0]) flag[u][0]=false;
34 if(flag[v][0]==false) flag[u][1]=false;
35 }
36 }
37
38 int main(){
39 string na1, na2;
40 while(scanf("%d", &n) && n){
41 mp.clear();
42 memset(g, 0, sizeof(g));
43 cnt=0;
44 cin>>na1;
45 mp[na1]=++cnt;
46 for(int i=1; i<n; ++i){
47 dp[i][1]=1;
48 dp[i][0]=0;
49 flag[i][1]=flag[i][0]=true;
50 cin>>na1>>na2;
51 it=mp.find(na1);
52 if(it==mp.end())
53 mp[na1]=++cnt;
54 it=mp.find(na2);
55 if(it==mp.end())
56 mp[na2]=++cnt;
57 g[mp[na2]][mp[na1]]=1;
58 }
59 dp[n][1]=1;
60 dp[n][0]=0;
61 flag[n][1]=flag[n][0]=true;
62 dfs(1);
63 if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s
", dp[1][1], "Yes");
64 else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s
", dp[1][0], "Yes");
65 else printf("%d %s
", max(dp[1][0], dp[1][1]), "No");
66 }
67 return 0;
68 }