#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
 
 
#define MAXLINE 40
 
struct nodo_arbol	{
	struct nodo_arbol *padre,*derecho,*izquierdo;	// 12 u 24 bytes
	int valor;										// 4 bytes
};									//Total				16 u 28 bytes por Nodo
									//peor Caso 28 bytes * 100,000 nodos = ~2.8 MB
 
struct nodo	{
	int id;						//4 bytes
	int *relations;				//4 ú 8 bytes
	int total;					//4 bytes
	struct nodo_arbol *arbol;	//4 ú 8 bytes
	int offset;
	int visitado;
};					//Total			16 u 24 bytes por Nodo
					///peor Caso 24 bytes * 100,000 nodos = ~2.40 MB
 
struct nodo **todos = NULL;	//Futuro arreglo de todos los nodos existente
							//4 y 8 bytes
							//Peor caso 8 bytes * 100,000   = ~800 KB	
 
void add_relation(int A,int B);
bool existe_salto(int A,int B);
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor);
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor);
 
 
int main()	{
	FILE *in = NULL;
	char *line = NULL;
	char *delim = " \n";
	char *token;
	char caso;
	int N,M,i,A,B;
	in = fopen("amistad.in","r");	//Archivo ¬¬
	srand(time(NULL));	// Para los nodos visitados...
	line = calloc(MAXLINE,1);
	//Leemos la primera linea
	fgets(line,MAXLINE,in);
	token = strtok(line,delim);
	N = strtol(token,NULL,10);
	todos = calloc(sizeof(struct nodo*),N);		//Reservamos espacio para al menos N apuntadores a los nodos	
	token = strtok(NULL,delim);
	M = strtol(token,NULL,10);
	//Leemos las siguientes M lineas y evaluamos
	i = 0;
	while(i < M)	{
		memset(line,0,MAXLINE);
		//Leemos la M,esima linea
		fgets(line,MAXLINE,in);
		token = strtok(line,delim);
		caso = token[0];
		token = strtok(NULL,delim);
		A = strtol(token,NULL,10);
		A--;
		token = strtok(NULL,delim);
		B = strtol(token,NULL,10);
		B--;
		//Evaluamos
		switch(caso){
			case 'P':
				//printf("P %i %i\n",A+1,B+1);
				if(todos[A] && todos[B])	{	// Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
					if(existe_salto(A,B))	{
						printf("1\n");
					}
					else	{
						printf("0\n");
					}
				}
				else	{	// Uno de los nodos es NULL entonces no existe camino de A a B
					//printf("Un nodo es invalido\n");
					printf("0\n");
				}
			break;
			case 'S':
				//printf("S %i %i\n",A+1,B+1);
				add_relation(A,B);
			break;
		}
		i++;
	}
	fclose(in);
	return 0;
}
 
void add_relation(int A,int B)	{
	if(todos[A] != NULL)	{
		//Nodo ya inicializado;
		todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
		todos[A]->relations[todos[A]->total] = B;
		todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
		todos[A]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
	}
	else	{
		//Nodo no inicializado
		todos[A] = calloc(sizeof(struct nodo),1);
		todos[A]->id  = A; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
		todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
		todos[A]->relations[todos[A]->total] = B;
		todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
		todos[A]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
		todos[A]->visitado = 0;
		todos[A]->offset = 0;
	}
	if(todos[B] != NULL)	{
		//Nodo ya inicializado;
		todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
		todos[B]->relations[todos[B]->total] = A;
		todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
		todos[B]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
 
	}
	else	{
		//Nodo no inicializado
		todos[B] = calloc(sizeof(struct nodo),1);
		todos[B]->id  = B; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
		todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
		todos[B]->relations[todos[B]->total] = A;
		todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
		todos[B]->total++;	//incrementamos el numero total de relaciones que tiene este nodo
		todos[B]->visitado = 0;
		todos[B]->offset = 0;
	}		
}
 
//A.k.a diskjtra simplificado a aristas de valor 1 y solo valida que exista la union
bool existe_salto(int A,int B)	{
	bool r = false,outs = false;
	struct nodo *nodo_a = NULL,*nodo_b =NULL,*inicio =NULL,*pivote = NULL;
	struct nodo_arbol *busqueda = NULL;
	struct nodo **pendientes = NULL;
	register int i,j,buscar,total = 0;
	int visitado;
	visitado = rand();
	nodo_a = todos[A];
	nodo_b = todos[B];
	if(nodo_a->total < nodo_b->total)	{
		inicio = nodo_a;
		buscar = B;
		//printf("Menor A %i\n",inicio->id+1);
	}
	else	{
		inicio = nodo_b;
		buscar = A;
		//printf("Menor B %i\n",inicio->id+1);
	}
	//printf("Nodos: "); 
	i = 0;
	pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
	pendientes[total] = inicio;
	total++;
	while(!r && i < total)	{
		pivote = pendientes[i];
		pivote->visitado = visitado;
		//printf("Visitando %i\n",pivote->id+1);
		busqueda = buscar_nodo_arbol(pivote->arbol,buscar);
		if(!busqueda)	{
			//printf("El nodo %i no tiene el nodo buscado %i\n",pivote->id+1,buscar+1);
			j = 0;
			while(j < pivote->total )	{
				if(todos[pivote->relations[j]]->visitado != visitado)	{
					//printf("Anexando el nodo %i para su posterior visita\n",todos[pivote->relations[j]]->id+1);
					pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
					pendientes[total] = todos[pivote->relations[j]];
					total++;
				}
				j++;
			}
		}
		else	{
			//printf("El nodo %i SI tiene el nodo buscado %i\n",pivote->id+1,buscar+1);
			r = true;
		}
		i++;
	}
	free(pendientes);
	return r;
}
 
//Funciones de Arbol (Solo como almacenamiento y busqueda rapida)
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor)	{
	struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
	if(n == NULL)	{
		printf("Error de Memoria\n");
		exit(0);
	}
	n->padre = padre;
	n->valor = valor;
	return n;
}
 
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor)	{
	struct nodo_arbol *temp,*pivote;
	int derecho = 0;
	if(arbol)	{
		temp =arbol;
		while(temp != NULL)	{
			pivote = temp;
			if(valor > temp->valor)	{
				temp = temp->derecho;
				derecho = 1;
			}
			else	{
				temp = temp->izquierdo;
				derecho = 0;
			}
		}
		temp = crear_nodo_arbol(pivote,valor);
		if(derecho)	{
			pivote->derecho = temp;
		}
		else	{
			pivote->izquierdo = temp;
		}
		return arbol;
	}
	else	{
		temp = crear_nodo_arbol(NULL,valor);
		return temp;
	}
}
 
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar)	{
	struct nodo_arbol *temp = NULL,*pivote = NULL;
	int entrar = 1;
	temp =arbol;
	while(entrar == 1  && temp != NULL)	{
		pivote = temp;
		if(valorAbuscar == temp->valor){
			entrar = 0;
		}
		else	{
			if(valorAbuscar > temp->valor)	{
				temp = temp->derecho;
			}
			else	{
				temp = temp->izquierdo;
			}
		}
	}
	return temp;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
 
#define MAXLINE 40
 
struct nodo_arbol	{
	struct nodo_arbol *padre,*derecho,*izquierdo;
	struct nodo *valor;
};
 
struct arbol	{
	struct nodo_arbol *raiz;
	struct nodo_arbol **nodos;
	int total;
};
 
struct nodo	{
	int id;
	struct arbol *arbol;
};
 
struct nodo **todos = NULL;
 
void add_relation(int A,int B);
bool existe_salto(int A,int B);
struct arbol *funciona_arbol(struct arbol *A,struct arbol *B);
 
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo *valor);
struct arbol *agregar_valor_arbol(struct arbol *arbol,struct nodo *valor);
 
int main()	{
	FILE *in = NULL;
	char *line = NULL;
	char *delim = " \n";
	char *token;
	char caso;
	int N,M,i,A,B;
	in = fopen("amistad.in","r");	//Archivo ¬¬
	srand(time(NULL));	// Para los nodos visitados...
	line = calloc(MAXLINE,1);
	//Leemos la primera linea
	fgets(line,MAXLINE,in);
	token = strtok(line,delim);
	N = strtol(token,NULL,10);
	todos = calloc(sizeof(struct nodo*),N);		//Reservamos espacio para al menos N apuntadores a los nodos	
	token = strtok(NULL,delim);
	M = strtol(token,NULL,10);
	//Leemos las siguientes M lineas y evaluamos
	i = 0;
	while(i < M)	{
		memset(line,0,MAXLINE);
		//Leemos la M,esima linea
		fgets(line,MAXLINE,in);
		token = strtok(line,delim);
		caso = token[0];
		token = strtok(NULL,delim);
		A = strtol(token,NULL,10);
		A--;
		token = strtok(NULL,delim);
		B = strtol(token,NULL,10);
		B--;
		//Evaluamos
		switch(caso){
			case 'P':
				//printf("P %i %i\n",A+1,B+1);
				if(todos[A] && todos[B])	{	// Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
					if(existe_salto(A,B))	{
						printf("1\n");
					}
					else	{
						printf("0\n");
					}
				}
				else	{	// Uno de los nodos es NULL entonces no existe camino de A a B
					//printf("Un nodo es invalido\n");
					printf("0\n");
				}
			break;
			case 'S':
				//printf("S %i %i\n",A+1,B+1);
				add_relation(A,B);
			break;
		}
		i++;
	}
	fclose(in);
	return 0;
}
 
void add_relation(int A,int B)	{
	struct nodo *nodo_a,*nodo_b;
	if(todos[A] == NULL)	{	// Si no existe A lo inicializamos
		todos[A] = calloc(sizeof(struct nodo),1);
		todos[A]->id  = A;
	}
	if(todos[B] == NULL)	{	// Si no existe B lo inicializamos
		todos[B] = calloc(sizeof(struct nodo),1);
		todos[B]->id  = B;
	}
	nodo_a = todos[A];	
	nodo_b = todos[B];
	if(!nodo_a->arbol && !nodo_b->arbol){	// Si ambos arboles son NULL los inicializamos
		nodo_a->arbol = agregar_valor_arbol(nodo_a->arbol,nodo_a);
		nodo_a->arbol = agregar_valor_arbol(nodo_a->arbol,nodo_b);
	}
	else	{
		if(nodo_a->arbol && !nodo_b->arbol)	{	//Si el arbol de A es valido y el de B no, agregamos B al arbol de A
			nodo_a->arbol =agregar_valor_arbol(nodo_a->arbol,nodo_b);
		}
		else	{
			if(!nodo_a->arbol && nodo_b->arbol){	//Si el arbol de B es valid y el de A no, agregamo A al arbol de B
				nodo_b->arbol =agregar_valor_arbol(nodo_b->arbol,nodo_a);
			}
			else{// En este punto ambos arboles son validos 
				if(nodo_a->arbol != nodo_b->arbol)	{	//Validamos si ambos arboles son distintos
					if(nodo_a->arbol->total < nodo_b->arbol->total)	{	// Evaluamos cual es el arbol con mejor coste de fusion
						nodo_b->arbol = funciona_arbol(nodo_b->arbol,nodo_a->arbol);	//Fucionamos el arbol de A en el arbol de B 
					}
					else	{
						nodo_a->arbol = funciona_arbol(nodo_a->arbol,nodo_b->arbol);	//Fucionamos el arbol de B en el arbol de A
					}
				}
			}
		}
	}
}
 
//Fucinamos el arbol B en el arbol A, y eliminamos B nodo por nodo y finalmente liberamos la estructura Arbol que usamos
struct arbol *funciona_arbol(struct arbol *A,struct arbol *B)	{
	int i = 0;
	while(i<B->total)	{
		B->nodos[i];
		A = agregar_valor_arbol(A,B->nodos[i]->valor);
		free(B->nodos[i]);
		i++;
	}
	free(B);
	return A;
}
 
 
//Evaluar si existe un camino valido de A a B, se reduce a validar si estan en el mismo Arbol o no
bool existe_salto(int A,int B)	{
	struct nodo *nodo_a = NULL,*nodo_b =NULL;
	nodo_a = todos[A];
	nodo_b = todos[B];
	return (nodo_a->arbol == nodo_b->arbol);
}
 
 
//Funcion auxiliar para crear un nodo de arbol
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo *valor)	{
	struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
	if(n == NULL)	{
		printf("Error de Memoria\n");
		exit(0);
	}
	n->padre = padre;
	n->valor = valor;
	return n;
}
 
//Agregamos un valor al arbol
struct arbol *agregar_valor_arbol(struct arbol *arbol,struct nodo *valor)	{
	struct nodo_arbol *temp,*pivote;
	int derecho = 0;
	if(arbol)	{
		temp =arbol->raiz;
		while(temp != NULL)	{
			pivote = temp;
			if(valor->id > temp->valor->id)	{
				temp = temp->derecho;
				derecho = 1;
			}
			else	{
				temp = temp->izquierdo;
				derecho = 0;
			}
		}
		temp = crear_nodo_arbol(pivote,valor);
		if(derecho)	{
			pivote->derecho = temp;
		}
		else	{
			pivote->izquierdo = temp;
		}
		valor->arbol = arbol;
		arbol->nodos = realloc(arbol->nodos,sizeof(struct nodo*)*(arbol->total+1));
		arbol->nodos[arbol->total] = temp;
	}
	else	{
		arbol = calloc(sizeof(struct arbol),1);
		arbol->raiz = crear_nodo_arbol(NULL,valor);
		arbol->nodos = realloc(arbol->nodos,sizeof(struct nodo_arbol*)*(arbol->total+1));
		arbol->nodos[arbol->total] = arbol->raiz;
		valor->arbol = arbol;
	}
	arbol->total++;
	return arbol;
}