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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#include <message.h>
#include "kollib.h"

#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,p,k) for(int i=(p); i<=(k); ++i)

/*struct Random
{
  enum { A = 1103515245, C = 12345, M = 1<<30 };
  uint64_t seed = 892374892;
  int operator()(){ return seed = (A*seed+C)%M; }
};*/

//Random rnd;
std::set<int> iset,qset;

void go(int a, int b)
{
  int d = 0;
  while(1)
  {
    d++;
    if(qset.count(b))
    {
      PutInt(0,d); d = 0; PutInt(0,b);
      if(iset.count(b)) break;
    }
    int c = FirstNeighbor(b);
    a = c==a ? SecondNeighbor(b) : c;
    std::swap(a,b);
  }
  PutInt(0,-1);
}

struct Graph
{
  struct Edge { int b,d; };
  struct Next { Edge E[2]; Next(){ E[0].b = -1; } };

  std::map<int,Next> G;
  void add(int a, int b, int d)
  { add_one(a,b,d); add_one(b,a,d); }
  void add_one(int a, int b, int d)
  {
    if(!G.count(a)) G[a] = Next();
    bool i = G[a].E[0].b!=-1 && G[a].E[0].b!=b;
    G[a].E[i] = Edge{b,d};
  }
};

int main()
{
  srand(86238723);
  int N = NumberOfNodes();
  int I = MyNodeId();
  int S = NumberOfStudents();
  int Q = NumberOfQueries();

  std::vector<int> init;
  REP(i,N) init.push_back(random()%S+1);
  //if(!I){ REP(i,N) printf("%d ",init[i]); puts(""); }
  for(auto i : init){ qset.insert(i); iset.insert(i); }
  FOR(i,1,Q)
  {
    qset.insert(QueryFrom(i));
    qset.insert(QueryTo(i));
  }

  go(init[I],FirstNeighbor(init[I]));
  go(init[I],SecondNeighbor(init[I]));
  Send(0);

  //fprintf(stderr,"done\n");
  if(!I)
  {
    Graph G;
    REP(i,N)
    {
      int J = Receive(-1);
      REP(_,2)
      {
        int a = init[J];
        while(1)
        {
          int d = GetInt(J);
          if(d==-1) break;
          int b = GetInt(J);
          //printf("from %d: %d->%d (%d)\n",J,a,b,d);
          G.add(a,b,d); a = b;
          //puts("added");
        }
      }
    }

    /*{
      int a=1,b=1; REP(_,S)
      {
        int i = G.G[b].E[0].b==a;
        int d = G.G[b].E[i].d;
        a = G.G[b].E[i].b;
        //printf("%d -> %d (%d)\n",b,a,d);
        std::swap(a,b);
      }
    }*/

    FOR(q,1,Q)
    {
      //printf("query %d\n",q);
      int d = 0;
      int a = QueryFrom(q), t = QueryTo(q);
      //if(a==t){ puts("0"); continue; }
      int b = a;
      while(b!=t)
      {
        int i = G.G[b].E[0].b==a;
        d += G.G[b].E[i].d;
        a = G.G[b].E[i].b;
        std::swap(a,b);
      }
      printf("%d\n",std::min(d,S-d));
    }
  }

  return 0;
}