Family Tree

Solución 1

Explicación

Al encontrar el ancestro común más cercano y las distancias del ancestro a las dos vacas, podemos identificar de forma única su parentesco.

Implementación

Complejidad temporal: $\mathcal{O}(N^3)$

PythonJavaC++


import sys
 
sys.stdin = open("family.in", "r")
sys.stdout = open("family.out", "w")
 
rel_num, cow_a, cow_b = input().split()
relations = []
 
for i in range(int(rel_num)):
	relations.append(input().split())
 
 
# obtiene la madre de la vaca (si existe)
def mother(cow):
	for r in relations:
		if r[1] == cow:
			return r[0]
	return None
 
 
# devuelve la distancia entre cow y cow2 (-1 si no hay parentesco)
def direct_anc_dist(cow, cow2):
	dist = 0
	while cow2 != None:
		if cow == cow2:
			return dist
		cow2 = mother(cow2)
		dist += 1
	return -1
 
 
# distancia de a al ancestro común
da = 0
cow = cow_a
while cow != None:
	# si encontramos un ancestro común
	if direct_anc_dist(cow, cow_b) != -1:
		break
	cow = mother(cow)
	da += 1
 
# si no existe un ancestro común
if cow == None:
	print("NOT RELATED")
	sys.exit()
 
"""
como encontramos un ancestro común, cow.
podemos llamar a direct_anc() para obtener la distancia
de b al ancestro común.
"""
db = direct_anc_dist(cow, cow_b)
 
"""
si están emparentadas por un ancestro común,
pero no por madre o tía, podemos devolver
COUSINS.
"""
if da > 1 and db > 1:
	print("COUSINS")
	sys.exit()
 
# si la distancia de cada vaca a su ancestro
# común es uno, son hermanas,
elif da == 1 and db == 1:
	print("SIBLINGS")
	sys.exit()
else:
	if da > db:
		da, db = db, da
		cow_b, cow_a = cow_a, cow_b
	print(cow_a, "is the ", end="")
 
	# restamos dos porque 1 corresponde a mother
	# y 2 a grandmother
	for _ in range(db - 2):
		print("great-", end="")
	if da == 0 and db > 1:
		print("grand-", end="")
	if da == 0:
		print("mother ", end="")
	else:
		print("aunt ", end="")
	print("of", cow_b)


import java.io.*;
import java.util.*;
 
 
public class FamilyTree {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader("family.in"));
		PrintWriter out = new PrintWriter("family.out");
 
		StringTokenizer st = new StringTokenizer(in.readLine());
		int relNum = Integer.parseInt(st.nextToken());
		String cowX = st.nextToken();
		String cowY = st.nextToken();
		String[][] relations = new String[relNum][];
		for (int i = 0; i < relNum; i++) { relations[i] = in.readLine().split(" "); }
		in.close();
 
		// distancia mínima entre el ancestro compartido y X e Y
		int minXDist = 0;
		int minYDist = 0;
		String commonAncestor = cowX;
		// intentamos encontrar el ancestro común de X e Y (o si no hay uno)
		while (commonAncestor != null) {
			if (getAncestorDistance(commonAncestor, cowY, relations) != -1) {
				minYDist = getAncestorDistance(commonAncestor, cowY, relations);
				break;
			}
			commonAncestor = getMother(commonAncestor, relations);
			minXDist++;
		}
 
		// si X e Y no tienen ancestros comunes, no están emparentadas
		if (commonAncestor == null) {
			out.println("NOT RELATED");
		}
		// si ambas distancias son mayores que uno, son primas
		else if (minXDist > 1 && minYDist > 1) {
			out.println("COUSINS");
		}
		// ambas distancias de 1 significa que son hermanas
		else if (minXDist == 1 && minYDist == 1) {
			out.println("SIBLINGS");
		}
		// si una es el ancestro, es un parentesco de (great-...) mother
		else if (minXDist == 0 || minYDist == 0) {
			boolean xIsAncestor = minXDist == 0;
			out.print(String.format("%s is the ", commonAncestor));
			for (int i = 0; i < (xIsAncestor ? minYDist : minXDist) - 2; i++) {
				out.print("great-");
			}
			if ((xIsAncestor ? minYDist : minXDist) > 1) { out.print("grand-"); }
			out.println(String.format("mother of %s", xIsAncestor ? cowY : cowX));
		}
		// en caso contrario, hay un parentesco de (great-great-...) aunt
		else {
			boolean auntIsX = minXDist == 1;
			out.print(String.format("%s is the ", auntIsX ? cowX : cowY));
			for (int i = 0; i < (auntIsX ? minYDist : minXDist) - 2; i++) {
				out.print("great-");
			}
			out.println(String.format("aunt of %s", auntIsX ? cowY : cowX));
		}
		out.close();
	}
 
	// encuentra la madre de un hijo dado entre esos pares (devuelve null si no
	// hay madre)
	private static String getMother(String child, String[][] relations) {
		for (String[] pair : relations) {
			if (child.equals(pair[1])) { return pair[0]; }
		}
		return null;
	}
 
	// devuelve la distancia entre start y end (-1 si no hay parentesco)
	private static int getAncestorDistance(String start, String end,
	                                       String[][] relations) {
		int dist = 0;
		while (end != null) {
			if (end.equals(start)) { return dist; }
			dist++;
			end = getMother(end, relations);
		}
		return -1;
	}
}


#include <fstream>
#include <string>
#include <vector>
 
using std::string;
using std::vector;
using Relation = std::pair<string, string>;
 
// encuentra la madre de un hijo dado entre esos pares (devuelve vacío si no hay madre)
string mother(const string &child, const vector<Relation> &relations) {
	for (const Relation &r : relations) {
		if (r.second == child) { return r.first; }
	}
	return "";
}
 
// devuelve la distancia entre start y end (-1 si no hay parentesco)
int ancestor_dist(const string &start,
                  string end,  // vamos a reasignar esta variable, así que no usamos referencia
                  const vector<Relation> &relations) {
	int dist = 0;
	while (end != "") {
		if (end == start) { return dist; }
		dist++;
		end = mother(end, relations);
	}
	return -1;
}
 
int main() {
	std::ifstream read("family.in");
	int rel_num;
	string cow_x;
	string cow_y;
	read >> rel_num >> cow_x >> cow_y;
	vector<Relation> relations(rel_num);
	for (int r = 0; r < rel_num; r++) {
		read >> relations[r].first >> relations[r].second;
	}
 
	// distancia mínima entre el ancestro compartido y X e Y
	int min_x_dist = 0;
	int min_y_dist = 0;
	string common_ancestor = cow_x;
	// intentamos encontrar el ancestro común de X e Y (o si no hay uno)
	while (!common_ancestor.empty()) {
		if (ancestor_dist(common_ancestor, cow_y, relations) != -1) {
			min_y_dist = ancestor_dist(common_ancestor, cow_y, relations);
			break;
		}
		common_ancestor = mother(common_ancestor, relations);
		min_x_dist++;
		// written << common_ancestor << '\n';
	}
 
	std::ofstream written("family.out");
	// si X e Y no tienen ancestros comunes, no están emparentadas
	if (common_ancestor.empty()) {
		written << "NOT RELATED\n";
	}
	// si ambas distancias son mayores que uno, son primas
	else if (min_x_dist > 1 && min_y_dist > 1) {
		written << "COUSINS\n";
	}
	// ambas distancias de 1 significa que son hermanas
	else if (min_x_dist == 1 && min_y_dist == 1) {
		written << "SIBLINGS\n";
	}
	// si una es el ancestro, es un parentesco de (great-...) mother
	else if (min_x_dist == 0 || min_y_dist == 0) {
		bool x_is_ancestor = min_x_dist == 0;
		int ancestor_dist = x_is_ancestor ? min_y_dist : min_x_dist;
		written << (x_is_ancestor ? cow_x : cow_y) << " is the ";
		for (int i = 0; i < ancestor_dist - 2; i++) { written << "great-"; }
		if (ancestor_dist > 1) { written << "grand-"; }
		written << "mother of " << (x_is_ancestor ? cow_y : cow_x) << '\n';
	}
	// en caso contrario, hay un parentesco de (great-great-...) aunt
	else {
		bool x_is_aunt = min_x_dist == 1;
		written << (x_is_aunt ? cow_x : cow_y) << " is the ";
		for (int i = 0; i < (x_is_aunt ? min_y_dist : min_x_dist) - 2; i++) {
			written << "great-";
		}
		written << "aunt of " << (x_is_aunt ? cow_y : cow_x) << '\n';
	}
}

Solución 2

Explicación

Similar a la solución 1, pero encontramos el ancestro común de las dos vacas de forma más eficiente.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

JavaC++Python


import java.io.*;
import java.util.*;
 
public class Family {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("family.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int N = Integer.parseInt(initial.nextToken());
		String[] cows = new String[] {initial.nextToken(), initial.nextToken()};
 
		Map<String, String> edge = new HashMap<>();
		for (int i = 0; i < N; i++) {
			StringTokenizer relation = new StringTokenizer(read.readLine());
			String v = relation.nextToken();
			String u = relation.nextToken();
			// Si v es madre de u, entonces hay una arista del nodo u al nodo
			// v.
			edge.put(u, v);
		}
 
		// Mapa de los ancestros de cada nodo y sus distancias
		Map<String, Integer>[] ancestors =
		    new HashMap[] {new HashMap<>(), new HashMap<>()};
		for (int c = 0; c < cows.length; c++) {
			// BFS para encontrar los ancestros de ambas vacas y la distancia a ellos
			String at = cows[c];
			ancestors[c].put(at, 0);
			while (edge.containsKey(at)) {
				String next = edge.get(at);
				ancestors[c].put(next, ancestors[c].get(at) + 1);
				at = next;
			}
		}
 
		String common = null;
		int dist0 = Integer.MAX_VALUE;  // distancia de la vaca 0 al ancestro común
		int dist1 = Integer.MAX_VALUE;  // y la distancia de la vaca 1
		for (var d0 : ancestors[0].entrySet()) {
			if (ancestors[1].containsKey(d0.getKey())) {
				int d1 = ancestors[1].get(d0.getKey());
				if (dist0 > d0.getValue() && dist1 > d1) {
					common = d0.getKey();
					dist0 = d0.getValue();
					dist1 = d1;
				}
			}
		}
 
		PrintWriter written = new PrintWriter("family.out");
		if (common == null) {
			written.println("NOT RELATED");
		} else if (common.equals(cows[0]) || common.equals(cows[1])) {
			written.printf("%s is the ", common);
			int dist = common.equals(cows[0]) ? dist1 : dist0;
			for (int i = 0; i < dist - 2; i++) { written.print("great-"); }
			if (dist > 1) { written.print("grand-"); }
			String young = common.equals(cows[0]) ? cows[1] : cows[0];
			written.printf("mother of %s", young);
		} else {
			if (dist0 == 1 || dist1 == 1) {
				if (dist0 == 1 && dist1 == 1) {
					written.println("SIBLINGS");
				} else {
					boolean auntIs0 = dist0 == 1;
					written.printf("%s is the ", auntIs0 ? cows[0] : cows[1]);
					for (int i = 0; i < (auntIs0 ? dist1 : dist0) - 2; i++) {
						written.print("great-");
					}
					written.printf("aunt of %s", auntIs0 ? cows[1] : cows[0]);
				}
			} else {
				written.println("COUSINS");
			}
		}
		written.close();
	}
}


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("family.in", "r", stdin);
	int N;
	vector<string> cows(2);
	cin >> N >> cows[0] >> cows[1];
 
	map<string, string> edge;
	for (int i = 0; i < N; ++i) {
		string u, v;
		cin >> v >> u;
		// Si v es madre de u, entonces hay una arista del nodo u al nodo v.
		edge[u] = v;
	}
 
	// Mapa de los ancestros de cada nodo y sus distancias
	vector<map<string, int>> ancestors(2);
	for (int c = 0; c < 2; c++) {
		// BFS para encontrar los ancestros de ambas vacas y la distancia a ellos
		string at = cows[c];
		ancestors[c][cows[c]] = 0;
		while (edge.count(at) != 0) {
			auto n = edge.find(at);
			ancestors[c][n->second] = ancestors[c][at] + 1;
			at = n->second;
		}
	}
 
	string common;
	int dist0 = INT32_MAX;  // distancia de la vaca 0 al ancestro común
	int dist1 = INT32_MAX;  // y la distancia de la vaca 1
	// Encontramos el ancestro común más bajo
	for (const pair<string, int> &d0 : ancestors[0]) {
		auto d1 = ancestors[1].find(d0.first);
		if (d1 != ancestors[1].end() && (dist0 > d0.second || dist1 > d1->second)) {
			common = d0.first;
			dist0 = d0.second;
			dist1 = d1->second;
		}
	}
 
	freopen("family.out", "w", stdout);
 
	if (common.empty()) {
		cout << "NOT RELATED";
	} else if (common == cows[1] || common == cows[0]) {
		if (common == cows[0]) {
			swap(cows[0], cows[1]);
			swap(dist0, dist1);
		}
		cout << cows[1] << " is the ";
		if (dist0 >= 2) {
			for (int i = 0; i < dist0 - 2; ++i) { cout << "great-"; }
			cout << "grand-";
		}
		cout << "mother of " << cows[0];
	} else {
		if (dist1 < dist0) {
			swap(dist1, dist0);
			swap(cows[1], cows[0]);
		}
		if (dist0 == 1) {
			if (dist1 == 1) {
				cout << "SIBLINGS";
			} else {
				cout << cows[0] << " is the ";
				for (int i = 0; i < dist1 - 2; ++i) { cout << "great-"; }
				cout << "aunt of " << cows[1];
			}
		} else {
			cout << "COUSINS";
		}
	}
	cout << endl;
}


with open("family.in") as read:
	cows = [None, None]
	N, cows[0], cows[1] = read.readline().split()
	N = int(N)
 
	edge = {}
	for _ in range(N):
		v, u = read.readline().split()
		edge[u] = v
 
# Mapa de los ancestros de cada nodo y sus distancias
ancestors = [{}, {}]
for c in range(2):
	at = cows[c]
	ancestors[c][cows[c]] = 0
	while at in edge:
		next_ = edge[at]
		ancestors[c][next_] = ancestors[c][at] + 1
		at = next_
 
common = None
dist0 = float("inf")
dist1 = float("inf")
for d0 in ancestors[0].items():
	if d0[0] in ancestors[1]:
		d1 = ancestors[1][d0[0]]
		if dist0 > d0[1] and dist1 > d1:
			common = d0[0]
			dist0 = d0[1]
			dist1 = d1
 
with open("family.out", "w") as written:
	if common is None:
		print("NOT RELATED", file=written)
	elif common == cows[0] or common == cows[1]:
		print(f"{common} is the ", end="", file=written)
 
		ancestors = dist1 if common == cows[0] else dist0
		for _ in range(ancestors - 2):
			print("great-", end="", file=written)
		if ancestors > 1:
			print("grand-", end="", file=written)
 
		young = cows[1] if common == cows[0] else cows[0]
		print(f"mother of {young}", file=written)
	else:
		if dist0 == 1 or dist1 == 1:
			if dist0 == 1 and dist1 == 1:
				print("SIBLINGS", file=written)
			else:
				aunt_is_0 = dist0 == 1
 
				aunt = cows[0] if aunt_is_0 else cows[1]
				print(f"{aunt} is the ", end="", file=written)
				for _ in range((dist1 if aunt_is_0 else dist0) - 2):
					print("great-", end="", file=written)
 
				young = cows[1] if aunt_is_0 else cows[0]
				print(f"aunt of {young}", file=written)
		else:
			print("COUSINS", file=written)

Solución 3

Explicación

Primero creamos un mapa de cada vaca a su padre. Ahora manejamos esto caso por caso.

Que $X$ e $Y$ sean hermanas es equivalente a que tengan el mismo padre.
Que $Y$ sea una *-mother de $X$ es equivalente a que $Y$ sea igual a algún ancestro de $X$ . Podemos iterar sobre los ancestros de $X$ empezando con nuestra vaca actual siendo $X$ y luego asignando repetidamente la vaca actual a su padre.
Que $Y$ sea una *-aunt de $X$ es equivalente a que $Y$ y algún ancestro de $X$ sean hermanas. Podemos manejar esto combinando los casos 1 y 2.
Podemos manejar que $X$ sea una *-mother de $Y$ y que $X$ sea una *-aunt de $Y$ intercambiando $X$ e $Y$ y aplicando la misma lógica.
Si los ancestros más antiguos de $X$ e $Y$ son el mismo, entonces están emparentadas.
En caso contrario, si no aplica ninguno de los casos anteriores, entonces $X$ e $Y$ no están emparentadas.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ifstream fin("family.in");
	ofstream fout("family.out");
 
	int N;
	string c1, c2;
	fin >> N >> c1 >> c2;
 
	map<string, string> par;
	for (int i = 0; i < N; ++i) {
		string x, y;
		fin >> x >> y;
		par[y] = x;
	}
 
	if (par.count(c1) && par.count(c2) && par.at(c1) == par.at(c2)) {
		fout << "SIBLINGS\n";
		return 0;
	}
 
	// si c2 es una *-mother o *-aunt de c1, imprimimos y salimos
	auto try_print = [&]() {
		string current_c1 = c1;
		int jumps = 0;
		while (true) {
			if (current_c1 == c2) {
				fout << c2 << " is the ";
				for (int i = 0; i < jumps - 2; ++i) fout << "great-";
				if (jumps > 1) fout << "grand-";
				fout << "mother";
				fout << " of " << c1;
				fout << "\n";
				return true;
			}
			if (par.count(current_c1) && par.count(c2) &&
			    par.at(current_c1) == par.at(c2)) {
				fout << c2 << " is the ";
				for (int i = 0; i < jumps - 1; ++i) fout << "great-";
				fout << "aunt";
				fout << " of " << c1;
				fout << "\n";
				return true;
			}
			if (!par.count(current_c1)) break;
			++jumps;
			current_c1 = par.at(current_c1);
		}
		return false;
	};
 
	if (try_print()) return 0;
	swap(c1, c2);
	if (try_print()) return 0;
 
	auto top_anc = [&](string s) {
		while (par.count(s)) s = par.at(s);
		return s;
	};
	if (top_anc(c1) == top_anc(c2)) fout << "COUSINS\n";
	else fout << "NOT RELATED\n";
}

Solución en video

Por Amogha Pokkulandra

Video de YouTube (CaGt8uCRNxU)

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
 
vector<string> m;
vector<string> d;
 
int main() {
	freopen("family.in", "r", stdin);
	freopen("family.out", "w", stdout);
 
	int lines;
	string cowx, cowy;
	cin >> lines >> cowx >> cowy;
	string out;
 
	for (int i = 0; i < lines; i++) {
		string mom, dot;
		cin >> mom >> dot;
		m.push_back(mom);
		d.push_back(dot);
	}
 
	vector<string> xAnc, yAnc;
	string cx = cowx, cy = cowy;
 
	while (find(d.begin(), d.end(), cx) != d.end()) {
		xAnc.push_back(cx);
		int tempX = distance(d.begin(), find(d.begin(), d.end(), cx));
		cx = m[tempX];
	}
	xAnc.push_back(cx);
 
	while (find(d.begin(), d.end(), cy) != d.end()) {
		yAnc.push_back(cy);
		int tempY = distance(d.begin(), find(d.begin(), d.end(), cy));
		cy = m[tempY];
	}
	yAnc.push_back(cy);
 
	string common;
	bool found = false;
	for (string x : xAnc) {
		if (found) {
			break;
		} else {
			for (string y : yAnc) {
				if (x == y) {
					common = x;
					found = true;
					break;
				}
			}
		}
	}
 
	if (common == "") {
		cout << ("NOT RELATED");
	} else {
		int xLvl = distance(xAnc.begin(), find(xAnc.begin(), xAnc.end(), common));
		int yLvl = distance(yAnc.begin(), find(yAnc.begin(), yAnc.end(), common));
 
		if (xLvl == yLvl && yLvl == 1) {
			cout << ("SIBLINGS");
		} else if (xLvl == yLvl || (xLvl > 1 && yLvl > 1)) {
			cout << ("COUSINS");
		} else if (xLvl > yLvl) {
			int diff = xLvl - yLvl;
			if (cowy == common) {
				if (diff == 1) {
					out = "mother";
				} else {
					for (int j = 0; j < diff - 2; j++) { out += "great-"; }
					out += "grand-mother";
				}
				cout << (cowy + " is the " + out + " of " + cowx);
			} else {
				if (diff == 1) {
					out = "aunt";
				} else {
					for (int k = 0; k < diff - 1; k++) { out += "great-"; }
					out += "aunt";
				}
				cout << (cowy + " is the " + out + " of " + cowx);
			}
		} else {
			int diff = yLvl - xLvl;
			if (cowx == common) {
				if (diff == 1) {
					out = "mother";
				} else {
					for (int j = 0; j < diff - 2; j++) { out += "great-"; }
					out += "grand-mother";
				}
				cout << (cowx + " is the " + out + " of " + cowy);
			} else {
				if (diff == 1) {
					out = "aunt";
				} else {
					for (int k = 0; k < diff - 1; k++) { out += "great-"; }
					out += "aunt";
				}
				cout << (cowx + " is the " + out + " of " + cowy);
			}
		}
	}
}


import java.io.*;
import java.util.*;
 
public class FamilyTree {
	public static List<String> m = new ArrayList<String>();
	public static List<String> d = new ArrayList<String>();
 
	public static void main(String[] args) throws IOException {
		PrintWriter pw = new PrintWriter(new File("family.out"));
		BufferedReader br = new BufferedReader(new FileReader(new File("family.in")));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int lines = Integer.parseInt(st.nextToken());
		String cowx = st.nextToken();
		String cowy = st.nextToken();
		String out = "";
 
		for (int i = 0; i < lines; i++) {
			st = new StringTokenizer(br.readLine());
			m.add(st.nextToken());
			d.add(st.nextToken());
		}
 
		List<String> xAnc = new ArrayList<String>();
		List<String> yAnc = new ArrayList<String>();
 
		String cX = cowx;
		String cY = cowy;
 
		while (d.contains(cX)) {
			xAnc.add(cX);
			cX = m.get(d.indexOf(cX));
		}
		xAnc.add(cX);
 
		while (d.contains(cY)) {
			yAnc.add(cY);
			cY = m.get(d.indexOf(cY));
		}
		yAnc.add(cY);
 
		List<String> comAnc = new ArrayList<String>(xAnc);
		comAnc.retainAll(yAnc);
 
		if (comAnc.isEmpty()) {
			System.out.println("NOT RELATED");
			pw.println("NOT RELATED");
		} else {
			String common = comAnc.get(0);
			int xLvl = xAnc.indexOf(common);
			int yLvl = yAnc.indexOf(common);
 
			if (xLvl == yLvl && yLvl == 1) {
				System.out.println("SIBLINGS");
				pw.println("SIBLINGS");
			} else if (xLvl == yLvl || (xLvl > 1 && yLvl > 1)) {
				System.out.println("COUSINS");
				pw.println("COUSINS");
			} else if (xLvl > yLvl) {
				int diff = xLvl - yLvl;
				if (cowy.equals(common)) {
					if (diff == 1) {
						out = "mother";
					} else {
						for (int j = 0; j < diff - 2; j++) { out += "great-"; }
						out += "grand-mother";
					}
					System.out.println(cowy + " is the " + out + " of " + cowx);
					pw.println(cowy + " is the " + out + " of " + cowx);
				} else {
					if (diff == 1) {
						out = "aunt";
					} else {
						for (int k = 0; k < diff - 1; k++) { out += "great-"; }
						out += "aunt";
					}
					System.out.println(cowy + " is the " + out + " of " + cowx);
					pw.println(cowy + " is the " + out + " of " + cowx);
				}
			} else {
				int diff = yLvl - xLvl;
				if (cowx.equals(common)) {
					if (diff == 1) {
						out = "mother";
					} else {
						for (int j = 0; j < diff - 2; j++) { out += "great-"; }
						out += "grand-mother";
					}
					System.out.println(cowx + " is the " + out + " of " + cowy);
					pw.println(cowx + " is the " + out + " of " + cowy);
				} else {
					if (diff == 1) {
						out = "aunt";
					} else {
						for (int k = 0; k < diff - 1; k++) { out += "great-"; }
						out += "aunt";
					}
					System.out.println(cowx + " is the " + out + " of " + cowy);
					pw.println(cowx + " is the " + out + " of " + cowy);
				}
			}
		}
		pw.close();
		br.close();
	}
}