/*****************************************************************************
 * Solution for Lab Test 1                                                   *
 * Author: Abhijit Das                                                       *
 * Date: October 06, 2009                                                    *
 *****************************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define MAXCITY 100

/* Part 1: Use adjacency matrix representation */
void readGraph ( int A[MAXCITY][MAXCITY], int *n, int *e )
{
   int i, j, u, v;

   /* Read number of vertices and number of edges */
   scanf("%d%d", n, e);

   /* Initialize adjacency matrix */
   for (i=0; i<*n; ++i) for (j=0; j<*n; ++j) A[i][j] = 0;

   /* Read edges one by one */
   for (i=0; i<*e; ++i) {
      scanf("%d%d", &u, &v);  /* Read vertices */
      A[u][v] = A[v][u] = 1;  /* Create links */
   }
}

/* Part 2: Find the busiest airport */
int busiest ( int A[MAXCITY][MAXCITY], int n )
{
   int i, j, max, u, deg;

   /* Find the node with highest degree */

   /* Initialize max and index of max */
   max = u = -1;

   for (i=0; i<n; ++i) {
      /* compute the degree of vertex i */
      deg = 0;
      for (j=0; j<n; ++j) if (A[i][j]) ++deg;

      /* if i has degree larger than the current maximum, record it */
      if (deg > max) {
         max = deg;
         u = i;
      }
   }

   return u;
}

/* Part 3: Find route between u and v by DFS */
int existsRoute ( int A[MAXCITY][MAXCITY], int n, int u, int v )
{
   int S[MAXCITY], TOS, visited[MAXCITY], i, j;

   /* initially no vertices are visited */
   for (i=0; i<n; ++i) visited[i] = 0;

   /* visit vertex u */
   S[0] = u; TOS = 0;
   visited[u] = 1;

   /* DFS loop */
   while (TOS >= 0) {
      /* v reached from u */
      if (S[TOS] == v) return 1;

      /* read top of stack and pop */
      i = S[TOS--];

      /* push all unvisited neighbors of i */
      for (j=0; j<n; ++j) {
         if ((A[i][j]) && (!visited[j])) {
            S[++TOS] = j;
            visited[j] = 1;
         }
      }
   }

   /* v was not reachable in the DFS from u */
   return 0;
}

/* Part 4: Check connectedness of graph by DFS */
int connected ( int A[MAXCITY][MAXCITY], int n )
{
   int S[MAXCITY], TOS, visited[MAXCITY], i, j, nvis;

   /* initially no vertices are visited */
   for (i=0; i<n; ++i) visited[i] = 0;

   /* DFS starts at vertex 0 */
   S[0] = 0; TOS = 0;
   visited[0] = 1; nvis = 1;

   /* DFS loop */
   while (TOS >= 0) {
      /* read top of stack and pop */
      i = S[TOS--];

      /* push all unvisited neighbors of i */
      /* also keep track of the count of visited vertices */
      for (j=0; j<n; ++j) {
         if ((A[i][j]) && (!visited[j])) {
            S[++TOS] = j;
            visited[j] = 1;
            ++nvis;
         }
      }
   }

   /* check whether all vertices are visited */
   return (nvis == n);
}

int main ()
{
   int n, e, u, v;
   int A[MAXCITY][MAXCITY];

   /* Part 1: Read flight schedule */
   readGraph(A,&n,&e);

   /* Part 2: Find the busiest airport */
   printf("The busiest airport is %d\n", busiest(A,n));

   /* Part 3: Find existence of route between u and v */
   scanf("%d%d", &u, &v);
   if (existsRoute(A,n,u,v))
      printf("Flight route exists between %d and %d\n", u, v);
   else
      printf("Flight route does not exist between %d and %d\n", u, v);

   /* Part 4: Find existence of route between any pair of cities */
   if (connected(A,n)) {
      printf("All pairs of cities are connected\n");

      /* Part 5: Check for multiple routes */
      if (e == n-1)
         printf("Every pair is connected by a unique route\n");
      else
         printf("Multiple routes exist among some cities\n");
   } else {
      printf("Some pairs of cities are not connected\n");
   }

   exit(0);
}