subject

L2-016 wish all lovers in the world are brothers and sisters who have been separated for many years (25 points)
ha-ha. We all know that intermarriage is not allowed within five clothes, that is, if the nearest common ancestor of two people is within five generations (i.e. myself, parents, grandparents, great grandparents and high grandparents), they cannot intermarry. Please help a couple to judge whether they can get married or not?

Input format:
The first line of input gives a positive integer N (2 ≤ N ≤ 10
4
), followed by N lines, each giving a person's information in the following format:

My ID gender father ID mother ID
The ID is 5 digits, which is different for each person; Gender M stands for male and F for female. If a person's father or mother is no longer available, the corresponding ID position is marked with - 1.

Next, a positive integer k is given, followed by K lines. Each line gives the ID s of a pair of lovers, separated by spaces.

Note: the title ensures that two people are of the same generation, each has only one gender, and there is no incest or marriage between generations in the blood relationship network.

Output format:
For each pair of lovers, judge whether their relationship can be intermarried: if they are of the same sex, output Never Mind; If it is heterosexual and related to five clothes, output Yes; If the heterosexual relationship does not produce 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
Sample output:
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

thinking

Use parallel search set to connect them, and use find to judge whether they have kinship, and finally use dfs (deep first search) to judge whether their kinship has exceeded five generations.
Note: there are some strange test data in the title, which may let you judge whether married people can be together. Therefore, the gender of each parent also needs to be marked.
The recursive implementation of find function will save more time and occupy more memory. It will be used more when the memory limit is small

code

#include<stdio.h>
typedef struct node{
	char sex;
	int fa;
	int mu;
}r; 
r a[100005];
int home[100005];

int init();
int find(int t);
void un(int a,int b);
int dfs(int p,int q,int age);
int main(){
	init();
	int n,k;
	int i;
	int x;
	scanf("%d",&n);
	char sex;
	int id,father,mather;
	for(i=0;i<n;i++){
		scanf("%d %c %d %d", &id, &sex, &father, &mather);
        a[id].fa = father;
        a[id].sex = sex;
        a[id].mu = mather;
        un(id, father);
        un(id, mather);
        if (father != -1)
            a[father].sex = 'M';
        if (mather != -1)
            a[mather].sex = 'F';	
	}
	int p,q;
	scanf("%d",&k);
	while(k--){
		scanf("%d %d",&p,&q);
		if(a[p].sex==a[q].sex){
			printf("Never Mind\n");
		}else{
			if(find(p)!=find(q)){
				printf("Yes\n");
			}else{
				if(dfs(p,q,1)){
					printf("Yes\n");
				}else{
					printf("No\n");
				}
			}
		}
	}
	
}
int init()
{
	for(int i=0;i<100005;i++){
		home[i]=i;
		a[i].fa=-1;
		a[i].mu=-1;
	}
}
int find(int t)
{
	if(t==home[t]){
		return t;
	}else{
		return home[t]=home[home[t]];
	}
}
void un(int a,int b)
{
	if(b==-1){
		return;
	}
	a=find(a);
	b=find(b);
	if(a>b){
		home[a]=b;
	}else{
		home[b]=a;
	}
	
}
int dfs(int p,int q,int age)
{
	if(p==-1||q==-1){
		return 1;
	}
	if(age>5){
		return 1;
	}
	if(p==q){
		return 0;
	}else{
		return dfs(a[p].fa,a[q].fa,age+1)&&dfs(a[p].fa,a[q].mu,age+1)&&dfs(a[q].fa,a[p].mu,age+1)&&dfs(a[p].mu,a[q].mu,age+1);
	}
}