Title Description:

Ha-ha. Everyone knows that no intermarriage is allowed within five clothes, that is, if the two people's closest common ancestors are within five generations (i.e. themselves, parents, grandparents, great-grandparents and high-grandparents), they can not intermarry. This question asks you to help a couple of loved ones judge whether they can marry or not.

Input format:

Input the first line to give a positive integer N (2 < N < 10 4), then N lines, each line gives a person's information in the following format:

My ID Sex Father ID Mother ID

Among them, ID is 5 digits, each person is different; gender M represents male, F represents female. If a person's father or mother is no longer available, the corresponding ID position is marked as - 1.

Next, a positive integer K is given, followed by K rows, each of which gives the ID of a couple of lovers, separated by spaces.

Note: The Title guarantees that two people are of the same generation, each of them has only one sex, and there is no incest or intergenerational marriage in the kinship network.

Output format:

For each couple, judge whether their relationship can be intermarried: if they are same sex, output Never Mind; if they are opposite sex and have five clothes, output Yes; if they have not five clothes, output No.

Input sample:

24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011

Output sample:

Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

Solution: I use structure to store relations, and then use two deep searches. The first time I mark the number of the first person's five-service internal relations. The second time is actually to see whether the number of the second person's five-service internal relations is marked. If it is marked, it is'No'. The most important thing to pay attention to is this question. The gender of father and mother should also be marked with the corresponding number. (This was discovered by reading a blog of a senior student.) ____________. Otherwise, it can't be all right.

AC code:

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct people
{
	int num;
	char sex;
	int f;
	int m;
};
struct people p[100002];
int flag[100002];
int flag1;
void dfs(int start,int num)
{
	if(num==5)
	{
		return;
	}
	else
	{
		if(p[start].f!=-1)
		{
			if(flag[p[start].f]==1)
			{
				flag1=1;
				return;
			}
			else
			{
				flag[p[start].f]=1;
				dfs(p[start].f,num+1);
			}
		}
		if(p[start].m!=-1)
		{
			if(flag[p[start].m]==1)
			{
				flag1=1;
				return;
			}
			else
			{
				flag[p[start].m]=1;
				dfs(p[start].m,num+1);
			}
		}
	}
	
}
int main(int argc, char *argv[]) {
	int a;
	scanf("%d",&a);
	for(int n=0;n<100002;n++)
	{
		p[n].f=-1;
		p[n].m=-1;
	}
	for(int n=0;n<a;n++)
	{
		int b,c,d;
		char x;
		scanf("%d %c %d %d",&b,&x,&c,&d);
		p[b].num=b;
		p[b].sex=x;
		p[b].f=c;
		p[b].m=d;
		if(c!=-1)
		{
			p[c].sex='M';
		}
		if(d!=-1)
		{
			p[d].sex='F';
		}
	}
	scanf("%d",&a);
	for(int n=0;n<a;n++)
	{
		int t1,t2;
		scanf("%d %d",&t1,&t2);
		flag1=0;
		memset(flag,0,sizeof(flag));
		if(p[t1].sex==p[t2].sex)
		{
			printf("Never Mind\n");
		}
		else
		{
			dfs(t1,1);
			dfs(t2,1);
			if(flag1==0)
			{
				printf("Yes\n");
			}
			else
			{
				printf("No\n");
			}
		}
	}
}