#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
#include<math.h>

using namespace std;

void delEm(int temp[], int x, int n)
{
 for (int i=0; i<n; i++)
  if (i == x) temp[i] = -1;
  
}

int fID(int graf[][15], int x, int n, int y )
{
     for(int i = y; i<n; i++)
     if (graf[i][x] == 1) { return i;break;}
     else {return -i;break;}
     
}

int checked(int temp[], int ud)
{
  if (temp[ud] == -1) return 0;
   else return 1;  
    }
int check(int temp[], int n)
{
    int ce = 0;
    
    for(int i=0; i<n; i++)
    if (temp[i] != -1)  ce++;
    
   
    
    if (ce == 0) return 0;
     else return 1;
     
    }

int main()
{   srand(time(NULL));

    int n,x, count=0, ud = 0,y = 0, k, ct = 0, ch, qp = 0;
    cout<<"Please, enter the numder of elements!"<<endl;
    cin>>n;
    
    int graf[15][15];// {{0,1,0,0,0,1},{1,0,1,0,1,1},{0,1,0,1,0,1},{0,0,1,0,0,0},{0,1,0,0,0,0},{1,1,1,0,0,0}}; 
    int temp[15];
    int tree[15][15];
    int mas[15];
    
    
    for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
        {
          if (i == j) graf[i][j] = 0;
          else 
          {
               graf[i][j] = rand()%2;    
               graf[j][i] = graf[i][j];
               }
              }  
              
    for(int i =0; i<n; i++)
      temp[i] = i;  
      
      for(int i =0; i<n; i++)
      mas[i] = '*';      
      
       
      
     for(int i =0; i<n; i++)
      for(int j = 0; j<n; j++)
      tree[i][j] = 0;   
            
    cout<<endl<<endl;
    
    for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
       {
           if (j == n-1) {cout<<graf[i][j]<<" "; cout<<endl;}
           else cout<<graf[i][j]<<" ";
           
           }
       
       cout<<endl<<endl;
           
  getch();
  
  x = rand()%n;
  cout<<"X = "<<x<<endl;
  
  mas[count] = x;
  count++;
  
  delEm(temp, x, n);  
  
    int key = 1;       
    int flag = 1;
    
    ct = count;
    
   while(key)
   {
   
             
    while(flag)
    {
    
   
           ud = fID(graf,x,n,y);
             
           if ((ud > -1)&&(graf[ud][x] == 1))
           {  
                 
                   k = checked(temp,ud);
                  if (k == 1) 
                 {
                  mas[ct] = ud;
                  tree[x][ud] = 1;
                  ct++;
                 // y = ud + 1;
                  delEm(temp, ud, n);
                  qp++;
                  
                  }
           }      
            
            y = abs(ud) + 1;
           
          
       
    if(y == n) flag = 0;
    else flag = 1;
             
      
          
      }
      
      ch = check(temp,n);
      if (ch == 0) key = 0;
       else key = 1;
      
  
      x = mas[count];
      ct = qp;
      ct++;
      count++;

      flag = 1;
      y = 0;
      
      
      } 
     
      for (int i = 0; i < n; i++)
       for (int j = 0; j < n; j++)
       {
           if (j == n-1) {cout<<tree[i][j]<<" "; cout<<endl;}
           else cout<<tree[i][j]<<" ";
           
           }
           
       cout<<endl; 
      
   getch(); 
  system("cls");	
  return 0;
}