/*##########################################################
# Yohann Gentile 552-55-3111                               #
# This is Prog3, a disjoint set program. This will take in #
# input of the following nature:                           #
#                                                          #
# 3                                                        #
# 3                                                        #
# 1 2   25                                                 #
# 1 3   25                                                 #
# 2 3   25                                                 #
#                                                          #
# The first two numbers are the number of vertices and     #
# edges. Every line after that enters in two vertices and  #
# the weight of their respective edge. After that, queries #
# can be made to see if two verices are connected.         #
#                                                          #
# 1 3                                                      #
# 1 2                                                      #
#                                                          #
# Finish this with a control-D. The Program will output    #
# if the vertices are connected or not   		   #
##########################################################*/

#include "myinclude.h"
#include "disjointset.h"


/* Function PROTOTYPES
 */
void SetToNull(SetElementHndl SetArray[100]);
int  CalculateInput(SetElementHndl SetArray[100], int WeightMatrix[100][100]);
void ProcessQueries(SetElementHndl SetArray[100]);
void FreeArray(SetElementHndl SetArray[100]);

void main()
{
  SetElementHndl SetArray[100];  /* We can have a maximum of 101 elements */
  int WeightMatrix[100][100];    /* I'm giving a maximum of a 100X100 matrix */
				 /* to store the weighted edges. */
  int TotalElements;

  SetToNull(SetArray);
  TotalElements = CalculateInput(SetArray, WeightMatrix);
  ProcessQueries(SetArray);
  FreeArray(SetArray);
}

/* SetToNull will go through the entire array and set each element
   to NULL.
*/
void SetToNull(SetElementHndl SetArray[100])
{
  int i;

  for(i = 0; i <= 100; i++){
    SetArray[i] = NULL;
  }
}

/* CalculateInput receives the initial data concerning the graph and returns
   the number of elements, or vertices with connecting edges it reads. This
   function is responsible for calling makeset for each entry.
*/
int CalculateInput(SetElementHndl SetArray[100], int WeightMatrix[100][100])
{
  int i, Edges, Vertices, Weight, Vertex1, Vertex2;

  scanf(" %d %d", &Vertices, &Edges);
  for(i = 1 ; i <= Edges; i++){
    scanf(" %d %d %d", &Vertex1, &Vertex2, &Weight);
    if(SetArray[Vertex1] == NULL)
      MakeSet(Vertex1, &SetArray[Vertex1]);
    if(SetArray[Vertex2] == NULL)
      MakeSet(Vertex2, &SetArray[Vertex2]);
    WeightMatrix[Vertex1][Vertex2] = Weight;
    WeightMatrix[Vertex2][Vertex1] = Weight;     /* The Matrix Is Symmetric */
    Union(SetArray[Vertex1], SetArray[Vertex2]);
  }
  return(Edges);
}

/* ProcessQueries reads in the query data and processes it into a matrix.
   It will then check to see if the two vertices are connected.
*/
void ProcessQueries(SetElementHndl SetArray[100])
{
  int QueryMatrix[100][2], i = 0, k;

  while(!feof(stdin)){
    scanf(" %d %d", &QueryMatrix[i][1], &QueryMatrix[i][2]);
    i++;
  }
  for(k = 0; k < i - 1; k++){
    if(SetArray[QueryMatrix[k][1]] == NULL || SetArray[QueryMatrix[k][2]]
	== NULL || FindSet(SetArray[QueryMatrix[k][1]]) !=
	FindSet(SetArray[QueryMatrix[k][2]]))
      printf("%d and %d are NOT connected.\n", QueryMatrix[k][1],
		QueryMatrix[k][2]);
      else
	printf("%d and %d are connected.\n", QueryMatrix[k][1],
		QueryMatrix[k][2]);
  }
}

/* FreeArray Frees all of the SetArray elements and points them back to NULL
*/
void FreeArray(SetElementHndl SetArray[100])
{
  int i;

  for(i = 0; i <= 100; i++){
    if(SetArray[i] != NULL) FreeSet(SetArray[i]);
  }
}