1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include "message.h"
#include "kollib.h"
#include <iostream>
#include<set>
#include<map>
//#include<stdlib.h>
using namespace std;
#define M 202

int main() {
  int AA[M][M]={{0}};
  int A[2*M]={0};
  int a, b, s, temp, first, inst, R, prev, ans, k, kk, f, where1;
  int Nu=NumberOfNodes(), n=NumberOfStudents(), m=NumberOfQueries();
  set<int> inout;
  for(int i=1; i<=m; ++i) {
    inout.insert(QueryFrom(i));   
    inout.insert(QueryTo(i));
    //WE
    //Wy
  }
  R=inout.size();
  k=1;
  map<int,int> which;
  for (set<int>::iterator it=inout.begin(); it!=inout.end(); ++it){
    A[k]=*it;
    which[*it]=k;
    k++;
  }
  int next1[2*M] = {0}, next2[2*M] = {0};

  for(int i=1+MyNodeId(); i<=R; i+=Nu ) {
    s=1;
    a=A[i];
    first=FirstNeighbor(a);
    while(inout.find(first)==inout.end()) {
      temp=first;
      if(FirstNeighbor(first)!=a)  first=FirstNeighbor(first);
      else                         first=SecondNeighbor(first);
      a=temp;
      s+=1;
    }
    s=min(s,n-s);
    f=which[first];
    where1=1;
    if (MyNodeId()>0) { PutInt(0, s);  PutInt(0, i);  PutInt(0, f);  PutInt(0, where1);  Send(0); } 
    else              { AA[i][f]=s;    AA[f][i]=s;    next1[i]=f ;                                }
    
    s=1;
    a=A[i];
    first=SecondNeighbor(a);
    while(inout.find(first)==inout.end()) {
      temp=first;
      if(FirstNeighbor(first)!=a)  first=FirstNeighbor(first);
      else first=SecondNeighbor(first);
      a=temp;
      s+=1;
    }
    s=min(s,n-s);
    f=which[first];
    where1=2;
    if (MyNodeId()>0) { PutInt(0, s);  PutInt(0, i);  PutInt(0, f);  PutInt(0, where1);  Send(0); } 
    else              { AA[i][f]=s;    AA[f][i]=s;    next2[i]=f ;                                }
  }
  
  if(MyNodeId()==0) {
  for (int j=1; j<=R-((R-1)/Nu+1); j++ ) {
    inst = Receive(-1);
    s= GetInt(inst);    k= GetInt(inst);    f= GetInt(inst);     where1=GetInt(inst);
    AA[k][f]=s;
    AA[f][k]=s;
    if(where1==1)
      next1[k]=f;
    else
      next2[k]=f;
    
     inst = Receive(-1);
    s= GetInt(inst);    k= GetInt(inst);    f= GetInt(inst);     where1=GetInt(inst);
    AA[k][f]=s;
    AA[f][k]=s;
    if(where1==1)
      next1[k]=f;
    else
      next2[k]=f;
  }

  k=1;
  prev=1;
  do {
    if(next1[k]==prev)
      next1[k]=next2[k];
    prev=k;
    k=next1[k];    
  }
  while(k!=1); 
  
  for (int i=1; i<=m; i++ ) {
    k=which[QueryFrom(i)];
    ans=0;
    while(k!=which[QueryTo(i)]){
      kk=next1[k];   
      ans+=AA[k][kk];
      k=kk;
    }
    ans=min(ans,n-ans);
    cout<<ans<<endl;
  }  
  }
  return(0);
}