#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <utility>
#include <stack>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define MP make_pair
#define FOR(v,p,k) for(int v=(p);v<=(k);++v)
#define FORD(v,p,k) for(int v=(p);v>=(k);--v)
#define REP(i,n) for(int i=0;i<(n);++i)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
#define ALL(c) c.begin(),c.end()

#define ODD(x) ((x)%2)
#define EVEN(x) (!(ODD(x)))

#include "kollib.h"
#include "message.h"
int p = 100000;


#include <set>
#include <map>

VI points;
set<int> pointsSet;

struct query {
  int from, to;
};

query queries[209];

struct student {
  int nr;
  PII distantNeighbors[2];
  int dst;
  student(int nr_, PII n1_, PII n2_) {
    nr = nr_;
    distantNeighbors[0] = n1_;
    distantNeighbors[1] = n2_;
    dst = 0;
  }

  student(int nr_, int node) {
    nr = nr_;
    int d,n;
    d = GetInt(node);
    n = GetInt(node);
    distantNeighbors[0] = MP(d,n);
    d = GetInt(node);
    n = GetInt(node);
    distantNeighbors[1] = MP(d,n);
    dst = 0;
  }

};

int main() {
  int nodesNumber = NumberOfNodes();
  int nodeID = MyNodeId();
  int n = NumberOfStudents();

  p = min(p,n);
  points.reserve(p);

  int queriesNumber = NumberOfQueries();
  if (queriesNumber == 0) return 0;

  FOR(i,1,queriesNumber) {
    int from = QueryFrom(i);
    int to = QueryTo(i);
    queries[i-1].from = from;
    queries[i-1].to = to;

    if (pointsSet.count(from) == 0) {
      pointsSet.insert(from);
      points.PB(from);
    }
    if (pointsSet.count(to) == 0) {
      pointsSet.insert(to);
      points.PB(to);
    }
  }
  if (n <= 2*p) {
    int i = 1;
    while (points.size() < p) {
      if (pointsSet.count(i) == 0) {
        pointsSet.insert(i);
        points.PB(i);
      }
      ++i;
    }
  } else {
    unsigned a = 1664525;
    unsigned c = 1013904223;
    unsigned x = 1400271458;
    while (points.size() < p) {
      int cand = (x%n)+1;
      x = x*a + c;
      if (pointsSet.count(cand)) continue;
      pointsSet.insert(cand);
      points.PB(cand);
    }
  } 

  vector<student> students;
  students.reserve(nodeID? p/nodesNumber + 1 : p);
  for (int i = nodeID; i < p; i += nodesNumber) {
    int start = points[i];
    int next = FirstNeighbor(start);
    int prev = start;
    int dist = 1;
    
    while (pointsSet.count(next) == 0) {
      int candNext = FirstNeighbor(next);
      if (candNext == prev) {
        candNext = SecondNeighbor(next);
      }
      prev = next;
      next = candNext;
      ++dist;
    }
    int dist1 = dist;
    int next1 = next;
    next = SecondNeighbor(start);
    prev = start;
    dist = 1;

    while (pointsSet.count(next) == 0) {
      int candNext = FirstNeighbor(next);
      if (candNext == prev) {
        candNext = SecondNeighbor(next);
      }
      prev = next;
      next = candNext;
      ++dist;
    }
    students.PB(student(start, MP(dist1, next1), MP(dist, next)));
  }

  if (nodeID > 0) {
    if (students.size() == 0) return 0;
    for (int i=0; i<students.size(); i++) {
      const student& s = students[i];
      PutInt(0, s.distantNeighbors[0].first);
      PutInt(0, s.distantNeighbors[0].second);
      PutInt(0, s.distantNeighbors[1].first);
      PutInt(0, s.distantNeighbors[1].second);
    }
    Send(0);
    return 0;
  } else {
    while(students.size() < p) {
      int connectedNode = Receive(-1);
      for (int i = connectedNode; i < p; i += nodesNumber) {
        int start = points[i];
        students.PB(student(start, connectedNode));
      }
    }
  }


  
  //TODO optymalniej
  map<int, int> studentIndex;
  REP(i,p) {
    studentIndex[students[i].nr] = i;
  }


  int next = 0;
  int prev = next;
  int dist = 0; 

  REP(i,p-1) {
    int candNext = studentIndex[students[next].distantNeighbors[0].second];
    if (candNext == prev) {  
      candNext = studentIndex[students[next].distantNeighbors[1].second];
      dist += students[next].distantNeighbors[1].first;
    } else {
      dist += students[next].distantNeighbors[0].first;
    }
    students[candNext].dst = dist;
    prev = next;
    next = candNext;
  }

  
  REP(i,queriesNumber) {
    int distFrom = students[studentIndex[queries[i].from]].dst;
    int distTo = students[studentIndex[queries[i].to]].dst;
    int ret = abs(distTo - distFrom);
    printf("%d\n", min(ret, n-ret));
  }

  return 0;
}