#include<iostream>
using namespace std;
 
class vertex;
class Graph;
 
void BFS(Graph,int);
 
 
 
struct Edge{
      int E_num;
      vertex*first;
      vertex*second;
      Edge*enext;
};
 
struct node{
       Edge*data;          // node of edgelist inside a vertex
       node*next;          // Here we can also store vertex numbers to get adjacent vertices quickly.
};
 
class vertex{
      public:
       int V_num;
       node*E_in_front;
       node*E_in_rear;
       node*E_out_front;
       node*E_out_rear;
       vertex*vnext;
       int color;
       int label;
       int parent;
 
 
       vertex(){
                E_in_front = E_in_rear = NULL;
                E_out_front = E_out_rear = NULL;
                color = 0; // initially white.
                label = -1;
                parent = -1;
                cout<<"Prompt: vertex created"<<endl;
               }
 
       void insert_node_vin(Edge*x)
       {
            node*temp = new node;
            temp->data = x;
            temp->next = NULL;
            if(E_in_front == NULL)
            { 
              E_in_front = E_in_rear = temp;
              cout<<"pointer to Edge in vin inserted"<<endl;
              return;
            }
            E_in_rear->next = temp;
            E_in_rear = temp;
            cout<<"pointer to Edge in vin inserted"<<endl;
       }
 
       void insert_node_vout(Edge*x)
       {
            node*temp = new node;
            temp->data = x;
            temp->next = NULL;
            if(E_out_front == NULL)
            { 
              E_out_front = E_out_rear = temp;
              cout<<"pointer to Edge in vout inserted"<<endl;
              return;
            }
            E_out_rear->next = temp;
            E_out_rear = temp;
            cout<<"pointer to Edge in vin inserted"<<endl;
       }
 
 
 
};
 
 
 
class Graph{
 
  public:
 
  Edge*E_front;
  Edge*E_rear;
  vertex*V_front;
  vertex*V_rear;
 
 
      Graph(){
              E_front = E_rear = NULL;
              V_front = V_rear = NULL;
              cout<<"Graph is initialised"<<endl;
              }  
 
      void insert_edge(int v1, int v2, int num) // num = edge number input by user.
      {
           if(ispresent(v1))
           { 
             if(ispresent(v2))
             { // just create an edge with starting vertex v1 and ending v2.
               Edge*temp = new Edge;
               temp->E_num = num;
               vertex*temp1 = V_front;
               vertex*temp2 = V_front;
               while(temp1 != NULL)
               {
                 if(temp1->V_num == v1)
                 break;
                 temp1 = temp1->vnext;
               }
               while(temp2 != NULL)
               {
                 if(temp2->V_num == v2)
                 break;
                 temp2 = temp2->vnext;
               }
               E_rear->enext = temp;
               temp->enext = NULL;
               E_rear =  temp;
               temp1->insert_node_vout(temp);
               temp2->insert_node_vin(temp);
 
               temp->first = temp1;
               temp->second = temp2;
             }
             else
             {
                 Edge*temp = new Edge;
                 temp->E_num = num;
                 vertex*temp1 = V_front;
                 while(temp1 != NULL)
                 {
                 if(temp1->V_num == v1)
                 break;
                 temp1 = temp1->vnext;
                 }
                 E_rear->enext = temp;
                 temp->enext = NULL;
                 E_rear =  temp;
                 vertex*temp2 = new vertex;
                 temp2->V_num = v2;
                 V_rear->vnext = temp2;
                 temp2->vnext = NULL;
                 V_rear = temp2;
 
                 temp1->insert_node_vout(temp);
                temp2->insert_node_vin(temp);
 
                temp->first = temp1;
                temp->second = temp2;
               }
             }
             else // if v1 is not present.
             {
                 if(ispresent(v2))
                 {
                 Edge*temp = new Edge;
                 temp->E_num = num;
                 vertex*temp2 = V_front;
                 while(temp2 != NULL)
                 {
                 if(temp2->V_num == v2)
                 break;
                 temp2 = temp2->vnext;
                 }
                 E_rear->enext = temp;
                 temp->enext = NULL;
                 E_rear =  temp;
                 vertex*temp1 = new vertex;
                 temp1->V_num = v1;
                 V_rear->vnext = temp1;
                 temp1->vnext = NULL;
                 V_rear = temp1;
 
                 temp1->insert_node_vout(temp);
                 temp2->insert_node_vin(temp);
 
                 temp->first = temp1;
                 temp->second = temp2;
                 }
               else  // both v1 and v2 are not present. It means either there are no elements in graph or only v1 & v2 are not present.
               { 
                 Edge*temp = new Edge;
                 temp->E_num = num;
                 if(E_front  == NULL)
                 {
                   E_front = E_rear = temp;
                   temp->enext = NULL;
                 }
                 else
                 {
                    E_rear->enext = temp;
                    temp->enext = NULL;
                    E_rear =  temp; 
                 }
                 vertex*temp1 = new vertex;
                 temp1->V_num = v1;
                 vertex*temp2 = new vertex;
                 temp2->V_num = v2;
                 if(V_front  == NULL)
                 {
                   V_front = V_rear = temp1;
                   temp1->vnext = temp2;
                   temp2->vnext = NULL;
                   V_rear = temp2;
                 }
                 else
                 {
                     V_rear->vnext = temp1;
                     temp1->vnext = temp2;
                     temp2->vnext = NULL;
                     V_rear = temp2;
                 }
 
                 temp1->insert_node_vout(temp);
                 temp2->insert_node_vin(temp);
 
                 temp->first = temp1;
                 temp->second = temp2;
                 cout<<"both "<<v1<<" and "<<v2<<" inserted in graph along with their edge number "<<num<<endl;
               }
             }
           }                                    // End void insert_edge(v1,v2,num).
 
           bool ispresent(int v)
           {
                if(V_front == NULL)
                return false;
 
                vertex*temp = V_front;
                while(temp != NULL)
                {
                  if(temp->V_num == v)
                  return true;
                  temp = temp->vnext;
                }
                return false;
           }
 
           int label_vertex(int v)
           {
               vertex*temp = V_front;
               while(temp != NULL)
               {
                if(temp->V_num == v)
                return temp->label;
                temp = temp->vnext;
               }
 
               return 0;
           }
};                                               // END OF CLASS GRAPH.
 
int main()
{
    Graph G;
    int v1=-1,v2,edgenum;
    cin>>v1>>v2>>edgenum;
    while(v1 != -1)
    {
      G.insert_edge(v1,v2,edgenum);
      cin>>v1;
      if(v1==-1)
      break;
      cin>>v2>>edgenum;
    }
    /* Now we have to define three arrays:- color, label, parent. For that either of steps can be taken:
       i) use a data member size in class graph and increment with each vertex addition
       ii)use three more data member inside vertex class ,namely color, label, parent.
       We will be using ii) case as it is more complex to implement.
    */
    cout<<"Enter the vertices between whom shortest distance is to be find out: ";
    cin>>v1>>v2;
    /* Here we will label all the vertex to practice.Otherwise there is no need of this because start BFS from v1 and when we get v2 print its
       label & also no need of taking "label" as data member because we have to just ++ a variable initialise to 0 whenever we pop-out of 
       queue and no need of labelling all intermediate vertices.But we do it here.
    */
 
    BFS(G,v1); // as discussed above this would change to BFS(G,v1,v2) and just return shortest distance directly.
 
    int shortest_path = G.label_vertex(v2) - G.label_vertex(v1);
 
    cout<<"Shortest path between "<<v1<<" and "<<v2<<" is : "<<shortest_path<<endl;
    // WE CAN ALSO STATE THE PATH TAKEN.
    //system("pause");
    return 0;
}
 
struct queuenode{
       vertex*vpointer;
       queuenode*qnext;
};
 
class queue{
      public:
      queuenode*front;
      queuenode*rear;
      int length;
 
      queue(){ front = NULL;
               rear = NULL;
               length = 0;
      }
 
      void enqueue(vertex*x)
      {
           queuenode*newnode = new queuenode;
           newnode->vpointer = x;
           newnode->qnext = NULL;
           if(length==0)
           {
             front = rear = newnode;
             length++;
             cout<<"Enqueued "<<x->V_num<<endl;
             return;
           }
 
           rear->qnext = newnode;
           length++;
           rear = newnode;
           cout<<"Enqueued "<<x->V_num<<endl;
      }
 
      void dequeue(){
           if(front == NULL)
           return;
 
           queuenode*temp = front;
           front = front->qnext;
           cout<<"Dequeued "<<temp->vpointer->V_num<<endl;
           delete temp;
           length--;
 
      }
};
 
 
void BFS(Graph G, int v)
{
  vertex*temp = G.V_front;         // Here we have taken "." instead of "->" in G.V_front.This is because "->" is taken only when object 
  while(temp->V_num != v)          // is of pointer type, like Graph*G.Thanks!! 
  temp = temp->vnext;
 
  queue q;
  q.enqueue(temp);
  temp->color = 1;  // gray- visited once and push in queue.
  temp->label = 0;  // level of that element.
  while(q.length != 0)  // queue is not empty.
  {   
      queuenode*temp1 = q.front;
      node*temp2 = temp1->vpointer->E_out_front;
      while(temp2 != NULL)
      { if(temp2->data->second->color == 0)
        {
        q.enqueue(temp2->data->second);
        temp2->data->second->label = temp1->vpointer->label + 1;
        temp2->data->second->color = 1;
        temp2->data->second->parent = temp1->vpointer->V_num;
        }
        temp2 = temp2->next;
 
      }
      temp1->vpointer->color = 2;
      q.dequeue();
 
  }  
 
}
 
 
 

I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyB2ZXJ0ZXg7CmNsYXNzIEdyYXBoOwoKdm9pZCBCRlMoR3JhcGgsaW50KTsKCgoKc3RydWN0IEVkZ2V7CiAgICAgIGludCBFX251bTsKICAgICAgdmVydGV4KmZpcnN0OwogICAgICB2ZXJ0ZXgqc2Vjb25kOwogICAgICBFZGdlKmVuZXh0Owp9OwoKc3RydWN0IG5vZGV7CiAgICAgICBFZGdlKmRhdGE7ICAgICAgICAgIC8vIG5vZGUgb2YgZWRnZWxpc3QgaW5zaWRlIGEgdmVydGV4CiAgICAgICBub2RlKm5leHQ7ICAgICAgICAgIC8vIEhlcmUgd2UgY2FuIGFsc28gc3RvcmUgdmVydGV4IG51bWJlcnMgdG8gZ2V0IGFkamFjZW50IHZlcnRpY2VzIHF1aWNrbHkuCn07CgpjbGFzcyB2ZXJ0ZXh7CiAgICAgIHB1YmxpYzoKICAgICAgIGludCBWX251bTsKICAgICAgIG5vZGUqRV9pbl9mcm9udDsKICAgICAgIG5vZGUqRV9pbl9yZWFyOwogICAgICAgbm9kZSpFX291dF9mcm9udDsKICAgICAgIG5vZGUqRV9vdXRfcmVhcjsKICAgICAgIHZlcnRleCp2bmV4dDsKICAgICAgIGludCBjb2xvcjsKICAgICAgIGludCBsYWJlbDsKICAgICAgIGludCBwYXJlbnQ7CiAgICAgICAKICAgICAgIAogICAgICAgdmVydGV4KCl7CiAgICAgICAgICAgICAgICBFX2luX2Zyb250ID0gRV9pbl9yZWFyID0gTlVMTDsKICAgICAgICAgICAgICAgIEVfb3V0X2Zyb250ID0gRV9vdXRfcmVhciA9IE5VTEw7CiAgICAgICAgICAgICAgICBjb2xvciA9IDA7IC8vIGluaXRpYWxseSB3aGl0ZS4KICAgICAgICAgICAgICAgIGxhYmVsID0gLTE7CiAgICAgICAgICAgICAgICBwYXJlbnQgPSAtMTsKICAgICAgICAgICAgICAgIGNvdXQ8PCJQcm9tcHQ6IHZlcnRleCBjcmVhdGVkIjw8ZW5kbDsKICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAKICAgICAgIHZvaWQgaW5zZXJ0X25vZGVfdmluKEVkZ2UqeCkKICAgICAgIHsKICAgICAgICAgICAgbm9kZSp0ZW1wID0gbmV3IG5vZGU7CiAgICAgICAgICAgIHRlbXAtPmRhdGEgPSB4OwogICAgICAgICAgICB0ZW1wLT5uZXh0ID0gTlVMTDsKICAgICAgICAgICAgaWYoRV9pbl9mcm9udCA9PSBOVUxMKQogICAgICAgICAgICB7IAogICAgICAgICAgICAgIEVfaW5fZnJvbnQgPSBFX2luX3JlYXIgPSB0ZW1wOwogICAgICAgICAgICAgIGNvdXQ8PCJwb2ludGVyIHRvIEVkZ2UgaW4gdmluIGluc2VydGVkIjw8ZW5kbDsKICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgRV9pbl9yZWFyLT5uZXh0ID0gdGVtcDsKICAgICAgICAgICAgRV9pbl9yZWFyID0gdGVtcDsKICAgICAgICAgICAgY291dDw8InBvaW50ZXIgdG8gRWRnZSBpbiB2aW4gaW5zZXJ0ZWQiPDxlbmRsOwogICAgICAgfQogICAgICAgCiAgICAgICB2b2lkIGluc2VydF9ub2RlX3ZvdXQoRWRnZSp4KQogICAgICAgewogICAgICAgICAgICBub2RlKnRlbXAgPSBuZXcgbm9kZTsKICAgICAgICAgICAgdGVtcC0+ZGF0YSA9IHg7CiAgICAgICAgICAgIHRlbXAtPm5leHQgPSBOVUxMOwogICAgICAgICAgICBpZihFX291dF9mcm9udCA9PSBOVUxMKQogICAgICAgICAgICB7IAogICAgICAgICAgICAgIEVfb3V0X2Zyb250ID0gRV9vdXRfcmVhciA9IHRlbXA7CiAgICAgICAgICAgICAgY291dDw8InBvaW50ZXIgdG8gRWRnZSBpbiB2b3V0IGluc2VydGVkIjw8ZW5kbDsKICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgRV9vdXRfcmVhci0+bmV4dCA9IHRlbXA7CiAgICAgICAgICAgIEVfb3V0X3JlYXIgPSB0ZW1wOwogICAgICAgICAgICBjb3V0PDwicG9pbnRlciB0byBFZGdlIGluIHZpbiBpbnNlcnRlZCI8PGVuZGw7CiAgICAgICB9CiAgICAgICAKICAgICAgIAogICAgICAgCn07CgoKICAgICAgIApjbGFzcyBHcmFwaHsKICAgICAgCiAgcHVibGljOgogICAgICAgICAKICBFZGdlKkVfZnJvbnQ7CiAgRWRnZSpFX3JlYXI7CiAgdmVydGV4KlZfZnJvbnQ7CiAgdmVydGV4KlZfcmVhcjsKICAKICAKICAgICAgR3JhcGgoKXsKICAgICAgICAgICAgICBFX2Zyb250ID0gRV9yZWFyID0gTlVMTDsKICAgICAgICAgICAgICBWX2Zyb250ID0gVl9yZWFyID0gTlVMTDsKICAgICAgICAgICAgICBjb3V0PDwiR3JhcGggaXMgaW5pdGlhbGlzZWQiPDxlbmRsOwogICAgICAgICAgICAgIH0gIAogICAgICAgICAgICAgIAogICAgICB2b2lkIGluc2VydF9lZGdlKGludCB2MSwgaW50IHYyLCBpbnQgbnVtKSAvLyBudW0gPSBlZGdlIG51bWJlciBpbnB1dCBieSB1c2VyLgogICAgICB7CiAgICAgICAgICAgaWYoaXNwcmVzZW50KHYxKSkKICAgICAgICAgICB7IAogICAgICAgICAgICAgaWYoaXNwcmVzZW50KHYyKSkKICAgICAgICAgICAgIHsgLy8ganVzdCBjcmVhdGUgYW4gZWRnZSB3aXRoIHN0YXJ0aW5nIHZlcnRleCB2MSBhbmQgZW5kaW5nIHYyLgogICAgICAgICAgICAgICBFZGdlKnRlbXAgPSBuZXcgRWRnZTsKICAgICAgICAgICAgICAgdGVtcC0+RV9udW0gPSBudW07CiAgICAgICAgICAgICAgIHZlcnRleCp0ZW1wMSA9IFZfZnJvbnQ7CiAgICAgICAgICAgICAgIHZlcnRleCp0ZW1wMiA9IFZfZnJvbnQ7CiAgICAgICAgICAgICAgIHdoaWxlKHRlbXAxICE9IE5VTEwpCiAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICBpZih0ZW1wMS0+Vl9udW0gPT0gdjEpCiAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgdGVtcDEgPSB0ZW1wMS0+dm5leHQ7CiAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgd2hpbGUodGVtcDIgIT0gTlVMTCkKICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgIGlmKHRlbXAyLT5WX251bSA9PSB2MikKICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICB0ZW1wMiA9IHRlbXAyLT52bmV4dDsKICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICBFX3JlYXItPmVuZXh0ID0gdGVtcDsKICAgICAgICAgICAgICAgdGVtcC0+ZW5leHQgPSBOVUxMOwogICAgICAgICAgICAgICBFX3JlYXIgPSAgdGVtcDsKICAgICAgICAgICAgICAgdGVtcDEtPmluc2VydF9ub2RlX3ZvdXQodGVtcCk7CiAgICAgICAgICAgICAgIHRlbXAyLT5pbnNlcnRfbm9kZV92aW4odGVtcCk7CiAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICB0ZW1wLT5maXJzdCA9IHRlbXAxOwogICAgICAgICAgICAgICB0ZW1wLT5zZWNvbmQgPSB0ZW1wMjsKICAgICAgICAgICAgIH0KICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICBFZGdlKnRlbXAgPSBuZXcgRWRnZTsKICAgICAgICAgICAgICAgICB0ZW1wLT5FX251bSA9IG51bTsKICAgICAgICAgICAgICAgICB2ZXJ0ZXgqdGVtcDEgPSBWX2Zyb250OwogICAgICAgICAgICAgICAgIHdoaWxlKHRlbXAxICE9IE5VTEwpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgIGlmKHRlbXAxLT5WX251bSA9PSB2MSkKICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICB0ZW1wMSA9IHRlbXAxLT52bmV4dDsKICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgRV9yZWFyLT5lbmV4dCA9IHRlbXA7CiAgICAgICAgICAgICAgICAgdGVtcC0+ZW5leHQgPSBOVUxMOwogICAgICAgICAgICAgICAgIEVfcmVhciA9ICB0ZW1wOwogICAgICAgICAgICAgICAgIHZlcnRleCp0ZW1wMiA9IG5ldyB2ZXJ0ZXg7CiAgICAgICAgICAgICAgICAgdGVtcDItPlZfbnVtID0gdjI7CiAgICAgICAgICAgICAgICAgVl9yZWFyLT52bmV4dCA9IHRlbXAyOwogICAgICAgICAgICAgICAgIHRlbXAyLT52bmV4dCA9IE5VTEw7CiAgICAgICAgICAgICAgICAgVl9yZWFyID0gdGVtcDI7CiAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgdGVtcDEtPmluc2VydF9ub2RlX3ZvdXQodGVtcCk7CiAgICAgICAgICAgICAgICB0ZW1wMi0+aW5zZXJ0X25vZGVfdmluKHRlbXApOwogICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIHRlbXAtPmZpcnN0ID0gdGVtcDE7CiAgICAgICAgICAgICAgICB0ZW1wLT5zZWNvbmQgPSB0ZW1wMjsKICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgfQogICAgICAgICAgICAgZWxzZSAvLyBpZiB2MSBpcyBub3QgcHJlc2VudC4KICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICBpZihpc3ByZXNlbnQodjIpKQogICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICBFZGdlKnRlbXAgPSBuZXcgRWRnZTsKICAgICAgICAgICAgICAgICB0ZW1wLT5FX251bSA9IG51bTsKICAgICAgICAgICAgICAgICB2ZXJ0ZXgqdGVtcDIgPSBWX2Zyb250OwogICAgICAgICAgICAgICAgIHdoaWxlKHRlbXAyICE9IE5VTEwpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgIGlmKHRlbXAyLT5WX251bSA9PSB2MikKICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICB0ZW1wMiA9IHRlbXAyLT52bmV4dDsKICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgRV9yZWFyLT5lbmV4dCA9IHRlbXA7CiAgICAgICAgICAgICAgICAgdGVtcC0+ZW5leHQgPSBOVUxMOwogICAgICAgICAgICAgICAgIEVfcmVhciA9ICB0ZW1wOwogICAgICAgICAgICAgICAgIHZlcnRleCp0ZW1wMSA9IG5ldyB2ZXJ0ZXg7CiAgICAgICAgICAgICAgICAgdGVtcDEtPlZfbnVtID0gdjE7CiAgICAgICAgICAgICAgICAgVl9yZWFyLT52bmV4dCA9IHRlbXAxOwogICAgICAgICAgICAgICAgIHRlbXAxLT52bmV4dCA9IE5VTEw7CiAgICAgICAgICAgICAgICAgVl9yZWFyID0gdGVtcDE7CiAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgdGVtcDEtPmluc2VydF9ub2RlX3ZvdXQodGVtcCk7CiAgICAgICAgICAgICAgICAgdGVtcDItPmluc2VydF9ub2RlX3Zpbih0ZW1wKTsKICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgdGVtcC0+Zmlyc3QgPSB0ZW1wMTsKICAgICAgICAgICAgICAgICB0ZW1wLT5zZWNvbmQgPSB0ZW1wMjsKICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgIGVsc2UgIC8vIGJvdGggdjEgYW5kIHYyIGFyZSBub3QgcHJlc2VudC4gSXQgbWVhbnMgZWl0aGVyIHRoZXJlIGFyZSBubyBlbGVtZW50cyBpbiBncmFwaCBvciBvbmx5IHYxICYgdjIgYXJlIG5vdCBwcmVzZW50LgogICAgICAgICAgICAgICB7IAogICAgICAgICAgICAgICAgIEVkZ2UqdGVtcCA9IG5ldyBFZGdlOwogICAgICAgICAgICAgICAgIHRlbXAtPkVfbnVtID0gbnVtOwogICAgICAgICAgICAgICAgIGlmKEVfZnJvbnQgID09IE5VTEwpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgRV9mcm9udCA9IEVfcmVhciA9IHRlbXA7CiAgICAgICAgICAgICAgICAgICB0ZW1wLT5lbmV4dCA9IE5VTEw7CiAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgRV9yZWFyLT5lbmV4dCA9IHRlbXA7CiAgICAgICAgICAgICAgICAgICAgdGVtcC0+ZW5leHQgPSBOVUxMOwogICAgICAgICAgICAgICAgICAgIEVfcmVhciA9ICB0ZW1wOyAKICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgdmVydGV4KnRlbXAxID0gbmV3IHZlcnRleDsKICAgICAgICAgICAgICAgICB0ZW1wMS0+Vl9udW0gPSB2MTsKICAgICAgICAgICAgICAgICB2ZXJ0ZXgqdGVtcDIgPSBuZXcgdmVydGV4OwogICAgICAgICAgICAgICAgIHRlbXAyLT5WX251bSA9IHYyOwogICAgICAgICAgICAgICAgIGlmKFZfZnJvbnQgID09IE5VTEwpCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgVl9mcm9udCA9IFZfcmVhciA9IHRlbXAxOwogICAgICAgICAgICAgICAgICAgdGVtcDEtPnZuZXh0ID0gdGVtcDI7CiAgICAgICAgICAgICAgICAgICB0ZW1wMi0+dm5leHQgPSBOVUxMOwogICAgICAgICAgICAgICAgICAgVl9yZWFyID0gdGVtcDI7CiAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgIFZfcmVhci0+dm5leHQgPSB0ZW1wMTsKICAgICAgICAgICAgICAgICAgICAgdGVtcDEtPnZuZXh0ID0gdGVtcDI7CiAgICAgICAgICAgICAgICAgICAgIHRlbXAyLT52bmV4dCA9IE5VTEw7CiAgICAgICAgICAgICAgICAgICAgIFZfcmVhciA9IHRlbXAyOwogICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICB0ZW1wMS0+aW5zZXJ0X25vZGVfdm91dCh0ZW1wKTsKICAgICAgICAgICAgICAgICB0ZW1wMi0+aW5zZXJ0X25vZGVfdmluKHRlbXApOwogICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICB0ZW1wLT5maXJzdCA9IHRlbXAxOwogICAgICAgICAgICAgICAgIHRlbXAtPnNlY29uZCA9IHRlbXAyOwogICAgICAgICAgICAgICAgIGNvdXQ8PCJib3RoICI8PHYxPDwiIGFuZCAiPDx2Mjw8IiBpbnNlcnRlZCBpbiBncmFwaCBhbG9uZyB3aXRoIHRoZWlyIGVkZ2UgbnVtYmVyICI8PG51bTw8ZW5kbDsKICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgfQogICAgICAgICAgIH0gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBFbmQgdm9pZCBpbnNlcnRfZWRnZSh2MSx2MixudW0pLgogICAgICAgICAgIAogICAgICAgICAgIGJvb2wgaXNwcmVzZW50KGludCB2KQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKFZfZnJvbnQgPT0gTlVMTCkKICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgdmVydGV4KnRlbXAgPSBWX2Zyb250OwogICAgICAgICAgICAgICAgd2hpbGUodGVtcCAhPSBOVUxMKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICBpZih0ZW1wLT5WX251bSA9PSB2KQogICAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgICAgICAgdGVtcCA9IHRlbXAtPnZuZXh0OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgICAgIH0KICAgICAgICAgICAKICAgICAgICAgICBpbnQgbGFiZWxfdmVydGV4KGludCB2KQogICAgICAgICAgIHsKICAgICAgICAgICAgICAgdmVydGV4KnRlbXAgPSBWX2Zyb250OwogICAgICAgICAgICAgICB3aGlsZSh0ZW1wICE9IE5VTEwpCiAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKHRlbXAtPlZfbnVtID09IHYpCiAgICAgICAgICAgICAgICByZXR1cm4gdGVtcC0+bGFiZWw7CiAgICAgICAgICAgICAgICB0ZW1wID0gdGVtcC0+dm5leHQ7CiAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgICAgIH0KfTsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIEVORCBPRiBDTEFTUyBHUkFQSC4KICAgICAgICAgCmludCBtYWluKCkKewogICAgR3JhcGggRzsKICAgIGludCB2MT0tMSx2MixlZGdlbnVtOwogICAgY2luPj52MT4+djI+PmVkZ2VudW07CiAgICB3aGlsZSh2MSAhPSAtMSkKICAgIHsKICAgICAgRy5pbnNlcnRfZWRnZSh2MSx2MixlZGdlbnVtKTsKICAgICAgY2luPj52MTsKICAgICAgaWYodjE9PS0xKQogICAgICBicmVhazsKICAgICAgY2luPj52Mj4+ZWRnZW51bTsKICAgIH0KICAgIC8qIE5vdyB3ZSBoYXZlIHRvIGRlZmluZSB0aHJlZSBhcnJheXM6LSBjb2xvciwgbGFiZWwsIHBhcmVudC4gRm9yIHRoYXQgZWl0aGVyIG9mIHN0ZXBzIGNhbiBiZSB0YWtlbjoKICAgICAgIGkpIHVzZSBhIGRhdGEgbWVtYmVyIHNpemUgaW4gY2xhc3MgZ3JhcGggYW5kIGluY3JlbWVudCB3aXRoIGVhY2ggdmVydGV4IGFkZGl0aW9uCiAgICAgICBpaSl1c2UgdGhyZWUgbW9yZSBkYXRhIG1lbWJlciBpbnNpZGUgdmVydGV4IGNsYXNzICxuYW1lbHkgY29sb3IsIGxhYmVsLCBwYXJlbnQuCiAgICAgICBXZSB3aWxsIGJlIHVzaW5nIGlpKSBjYXNlIGFzIGl0IGlzIG1vcmUgY29tcGxleCB0byBpbXBsZW1lbnQuCiAgICAqLwogICAgY291dDw8IkVudGVyIHRoZSB2ZXJ0aWNlcyBiZXR3ZWVuIHdob20gc2hvcnRlc3QgZGlzdGFuY2UgaXMgdG8gYmUgZmluZCBvdXQ6ICI7CiAgICBjaW4+PnYxPj52MjsKICAgIC8qIEhlcmUgd2Ugd2lsbCBsYWJlbCBhbGwgdGhlIHZlcnRleCB0byBwcmFjdGljZS5PdGhlcndpc2UgdGhlcmUgaXMgbm8gbmVlZCBvZiB0aGlzIGJlY2F1c2Ugc3RhcnQgQkZTIGZyb20gdjEgYW5kIHdoZW4gd2UgZ2V0IHYyIHByaW50IGl0cwogICAgICAgbGFiZWwgJiBhbHNvIG5vIG5lZWQgb2YgdGFraW5nICJsYWJlbCIgYXMgZGF0YSBtZW1iZXIgYmVjYXVzZSB3ZSBoYXZlIHRvIGp1c3QgKysgYSB2YXJpYWJsZSBpbml0aWFsaXNlIHRvIDAgd2hlbmV2ZXIgd2UgcG9wLW91dCBvZiAKICAgICAgIHF1ZXVlIGFuZCBubyBuZWVkIG9mIGxhYmVsbGluZyBhbGwgaW50ZXJtZWRpYXRlIHZlcnRpY2VzLkJ1dCB3ZSBkbyBpdCBoZXJlLgogICAgKi8KICAgICAKICAgIEJGUyhHLHYxKTsgLy8gYXMgZGlzY3Vzc2VkIGFib3ZlIHRoaXMgd291bGQgY2hhbmdlIHRvIEJGUyhHLHYxLHYyKSBhbmQganVzdCByZXR1cm4gc2hvcnRlc3QgZGlzdGFuY2UgZGlyZWN0bHkuCiAgICAKICAgIGludCBzaG9ydGVzdF9wYXRoID0gRy5sYWJlbF92ZXJ0ZXgodjIpIC0gRy5sYWJlbF92ZXJ0ZXgodjEpOwogICAgCiAgICBjb3V0PDwiU2hvcnRlc3QgcGF0aCBiZXR3ZWVuICI8PHYxPDwiIGFuZCAiPDx2Mjw8IiBpcyA6ICI8PHNob3J0ZXN0X3BhdGg8PGVuZGw7CiAgICAvLyBXRSBDQU4gQUxTTyBTVEFURSBUSEUgUEFUSCBUQUtFTi4KICAgIC8vc3lzdGVtKCJwYXVzZSIpOwogICAgcmV0dXJuIDA7Cn0KCnN0cnVjdCBxdWV1ZW5vZGV7CiAgICAgICB2ZXJ0ZXgqdnBvaW50ZXI7CiAgICAgICBxdWV1ZW5vZGUqcW5leHQ7Cn07CgpjbGFzcyBxdWV1ZXsKICAgICAgcHVibGljOgogICAgICBxdWV1ZW5vZGUqZnJvbnQ7CiAgICAgIHF1ZXVlbm9kZSpyZWFyOwogICAgICBpbnQgbGVuZ3RoOwogICAgICAKICAgICAgcXVldWUoKXsgZnJvbnQgPSBOVUxMOwogICAgICAgICAgICAgICByZWFyID0gTlVMTDsKICAgICAgICAgICAgICAgbGVuZ3RoID0gMDsKICAgICAgfQogICAgICAKICAgICAgdm9pZCBlbnF1ZXVlKHZlcnRleCp4KQogICAgICB7CiAgICAgICAgICAgcXVldWVub2RlKm5ld25vZGUgPSBuZXcgcXVldWVub2RlOwogICAgICAgICAgIG5ld25vZGUtPnZwb2ludGVyID0geDsKICAgICAgICAgICBuZXdub2RlLT5xbmV4dCA9IE5VTEw7CiAgICAgICAgICAgaWYobGVuZ3RoPT0wKQogICAgICAgICAgIHsKICAgICAgICAgICAgIGZyb250ID0gcmVhciA9IG5ld25vZGU7CiAgICAgICAgICAgICBsZW5ndGgrKzsKICAgICAgICAgICAgIGNvdXQ8PCJFbnF1ZXVlZCAiPDx4LT5WX251bTw8ZW5kbDsKICAgICAgICAgICAgIHJldHVybjsKICAgICAgICAgICB9CiAgICAgICAgICAgCiAgICAgICAgICAgcmVhci0+cW5leHQgPSBuZXdub2RlOwogICAgICAgICAgIGxlbmd0aCsrOwogICAgICAgICAgIHJlYXIgPSBuZXdub2RlOwogICAgICAgICAgIGNvdXQ8PCJFbnF1ZXVlZCAiPDx4LT5WX251bTw8ZW5kbDsKICAgICAgfQogICAgICAgICAgICAgCiAgICAgIHZvaWQgZGVxdWV1ZSgpewogICAgICAgICAgIGlmKGZyb250ID09IE5VTEwpCiAgICAgICAgICAgcmV0dXJuOwogICAgICAgICAgIAogICAgICAgICAgIHF1ZXVlbm9kZSp0ZW1wID0gZnJvbnQ7CiAgICAgICAgICAgZnJvbnQgPSBmcm9udC0+cW5leHQ7CiAgICAgICAgICAgY291dDw8IkRlcXVldWVkICI8PHRlbXAtPnZwb2ludGVyLT5WX251bTw8ZW5kbDsKICAgICAgICAgICBkZWxldGUgdGVtcDsKICAgICAgICAgICBsZW5ndGgtLTsKICAgICAgICAgCiAgICAgIH0KfTsKCgp2b2lkIEJGUyhHcmFwaCBHLCBpbnQgdikKewogIHZlcnRleCp0ZW1wID0gRy5WX2Zyb250OyAgICAgICAgIC8vIEhlcmUgd2UgaGF2ZSB0YWtlbiAiLiIgaW5zdGVhZCBvZiAiLT4iIGluIEcuVl9mcm9udC5UaGlzIGlzIGJlY2F1c2UgIi0+IiBpcyB0YWtlbiBvbmx5IHdoZW4gb2JqZWN0IAogIHdoaWxlKHRlbXAtPlZfbnVtICE9IHYpICAgICAgICAgIC8vIGlzIG9mIHBvaW50ZXIgdHlwZSwgbGlrZSBHcmFwaCpHLlRoYW5rcyEhIAogIHRlbXAgPSB0ZW1wLT52bmV4dDsKICAKICBxdWV1ZSBxOwogIHEuZW5xdWV1ZSh0ZW1wKTsKICB0ZW1wLT5jb2xvciA9IDE7ICAvLyBncmF5LSB2aXNpdGVkIG9uY2UgYW5kIHB1c2ggaW4gcXVldWUuCiAgdGVtcC0+bGFiZWwgPSAwOyAgLy8gbGV2ZWwgb2YgdGhhdCBlbGVtZW50LgogIHdoaWxlKHEubGVuZ3RoICE9IDApICAvLyBxdWV1ZSBpcyBub3QgZW1wdHkuCiAgeyAgIAogICAgICBxdWV1ZW5vZGUqdGVtcDEgPSBxLmZyb250OwogICAgICBub2RlKnRlbXAyID0gdGVtcDEtPnZwb2ludGVyLT5FX291dF9mcm9udDsKICAgICAgd2hpbGUodGVtcDIgIT0gTlVMTCkKICAgICAgeyBpZih0ZW1wMi0+ZGF0YS0+c2Vjb25kLT5jb2xvciA9PSAwKQogICAgICAgIHsKICAgICAgICBxLmVucXVldWUodGVtcDItPmRhdGEtPnNlY29uZCk7CiAgICAgICAgdGVtcDItPmRhdGEtPnNlY29uZC0+bGFiZWwgPSB0ZW1wMS0+dnBvaW50ZXItPmxhYmVsICsgMTsKICAgICAgICB0ZW1wMi0+ZGF0YS0+c2Vjb25kLT5jb2xvciA9IDE7CiAgICAgICAgdGVtcDItPmRhdGEtPnNlY29uZC0+cGFyZW50ID0gdGVtcDEtPnZwb2ludGVyLT5WX251bTsKICAgICAgICB9CiAgICAgICAgdGVtcDIgPSB0ZW1wMi0+bmV4dDsKICAgICAgICAKICAgICAgfQogICAgICB0ZW1wMS0+dnBvaW50ZXItPmNvbG9yID0gMjsKICAgICAgcS5kZXF1ZXVlKCk7CiAgICAgIAogIH0gIAogICAgICAgICAKfQogICAgICAgICAKICAgCg==