#include<iostream>
#define N 100

using namespace std;


struct Node{
        
     int data;   
     Node *link;
      
     
       
        };
        
struct stack{
       Node* stackarray[N];
       int sp;
       
       
       };

stack s;        


struct Queue{
        Node* queuearray[N];
        int rear;
        int front;              
        };
        
Queue q;
Node Adjlist[9];
bool visited[9];



void construct(Node*,int);
void DFSh(int);
int push(stack *,Node*&);
void pop(stack *,Node*&);
int isempty(stack *);
int isfull(stack *);
void visit(Node*);
Node* findAdj(Node *);
void DFS(Node*);


int main(void){
    for(int i=1;i<=8;i++){
      Adjlist[i].link=NULL;
      Adjlist[i].data=i;}
      
    Node *head1=&Adjlist[1];
    Node *head2=&Adjlist[2];
    Node *head3=&Adjlist[3];
    Node *head4=&Adjlist[4];
    Node *head5=&Adjlist[5];
    Node *head6=&Adjlist[6];
    Node *head7=&Adjlist[7];
    Node *head8=&Adjlist[8];
    
    construct(head1,2);
    construct(head1,3);
    construct(head2,4);
    construct(head2,5);
    construct(head3,6);
    construct(head3,7);
    construct(head4,2);
    construct(head4,8);
    construct(head5,2);
    construct(head5,8);
    construct(head6,3);
    construct(head6,8);
    construct(head7,3);
    construct(head7,8);
    construct(head8,4);
    construct(head8,5);
    construct(head8,6);
    construct(head8,7);
    
    s.sp=-1;
     for(int i=1;i<=8;i++)  
      visited[i]=false;
      
      
    DFS(head1);
    
       return 0;
}

void construct(Node* ptr,int x){
      Node *ppp=new Node;
      ppp->data=x;
      ppp->link=NULL;
      
      while(ptr->link!=NULL){
                             
        ptr=ptr->link;
       
     }
     ptr->link=ppp;
     
     }

     
     
void DFSh(int v){
      visited[v]=true;
     
      cout<<"Visit Vertex:"<<v<<" "<<endl;
      Node *w;
      for(w=&Adjlist[v];w;w=w->link)
        if(!visited[w->data])
           DFSh(w->data);
     }


void DFS(Node *ptr){
      
      Node *Vx,*Vy;
      
      push(&s,ptr);
      while(!(isempty(&s))){
           
           pop(&s,Vx);              
        if(visited[Vx->data]==false){
             visit(Vx);
             Vy=findAdj(Vx);                 
                 while(Vy!=NULL){
                    push(&s,Vy);      
                    Vy=findAdj(Vx);          
                                 }             
                                 
                                 
                                 }               
                               
                               }                  
                          
                          
                          
                          }
     
     
     
     
     
     




void visit(Node *x){
     
      visited[x->data]=true;
      cout<<"Visit Vertex:"<<x->data<<" "<<endl;
     
     }
     
Node* findAdj(Node *ptr){
        Node *pk=NULL;
        ptr=ptr->link;
        
     while(ptr!=NULL){  
         if(visited[ptr->data]==false)
          return ptr;
          ptr=ptr->link;
          }
          
     return pk;
     
     }  
     
     
     
int push(stack *p,Node* &x){
     if(isfull(p))
     return 1;
     p->sp++;
     p->stackarray[p->sp]=x;
     
     }
     
void pop(stack *p,Node *&x){
     
     x=p->stackarray[p->sp--];     
     
      
     } 
     
int isempty(stack *p){
     if(p->sp==-1)
     return 1;
     else
     return 0;      
     }
     
int isfull(stack *p){
    if(p->sp==N-1)   
    return 1;
    else
    return 0;   
}