#include<stdio.h>
#include<stdlib.h>
#include<map>
#include<queue>

#include"message.h"
#include"kollib.h"

using namespace std;

//#define DEBUG

/** Metoda szukająca odległości pomiędzy dwoma studentami */
int find(int from, int to) {
#ifdef DEBUG
	fprintf(stderr,"Processing request for: %d-%d\n",from,to);
#endif
	if(from==to) return 0;

	int left=FirstNeighbor(from);
	int right=SecondNeighbor(from);
	if((left==to)||(right==to)) return 1;

	int dist=1;				// dystans
	int leftP=from;			// poprzednie wartości dla kroku w lewo
	int rightP=from;		// poprzednie wartosci dla kroku w prawo
	
	for(;;) {
		int n;
		++dist;
		
		n=FirstNeighbor(left);
		if(n==leftP) n=SecondNeighbor(left);
		leftP=left; left=n;
		if(left==to) return dist;
		
		n=SecondNeighbor(right);
		if(n==rightP) n=FirstNeighbor(right);
		rightP=right; right=n;
		if(right==to) return dist;
	}
}

struct Point {
	int from;
	int to;
	int to2;
	int dist;
	int dist2;
};

map<int,int> q;


inline int min(int a, int b) { return a<b?a:b; }


/** Idzie w jedną stronę, aż do napotkania jednego z ważnych miejsc */
Point walk(int pos, int prev) {
#ifdef DEBUG
	fprintf(stderr,"Processing walk form: %d\n",pos);
#endif
	Point r;
	r.dist=1;
	r.from=prev;
	
	for(;;){
		if(q.find(pos)!=q.end()) {
			r.to=pos;
			return r;
		}
		// wybreamy następnego, tak aby się nie cofać
		int next=FirstNeighbor(pos);
		if(next==prev) next=SecondNeighbor(pos);
		prev=pos; pos=next;
		r.dist++;
	}
}

map<int,Point> dat;

void addPoint(int from, int to, int dir, int dist) {
#ifdef DEBUG
	fprintf(stderr,"Adding point: %d -> %d (%d) = %d\n",from,to,dir,dist);
	if(from==to) {
		fprintf(stderr,"ERRROR\n");
		return;
	}
#endif
	map<int,Point>::iterator p=dat.find(from);
	Point d;
	if(p==dat.end()) {
		d.from=from;
		d.to=to;
		d.dist=dist;
		d.to2=-1;
		dat[from]=d;
	} else {
		d=p->second;
		if(d.to==to) return;	// już jest
		if(d.to2==-1) {
			d.to2=to;
			d.dist2=dist;
			dat[from]=d;
		}
	}
}

int mapWalk(int from, int to, int dir) {
	if(from==to) return 0;
	int prev=from;
	int dist=0;
	Point d=dat[from];
	if(dir>0) {
		from=d.to;
		dist=d.dist;
	} else {
		from=d.to2;
		dist=d.dist2;
	}
	while(from!=to) {
		d=dat[from];
		int next;
		if(d.to==prev) {
			next=d.to2;
			dist+=d.dist2;
		} else {
			next=d.to;
			dist+=d.dist;
		}
		prev=from;
		from=next;
	}
	return dist;
}

int main() {
#if 1
	if((NumberOfStudents()<500000)) {
		if(MyNodeId()==0) {
#ifdef DEBUG
			fprintf(stderr,"Signle mode\n");
#endif
			for(int i=1;i<=NumberOfQueries();++i) {
				printf("%d\n",find(QueryFrom(i),QueryTo(i)));
			}
		}
		return 0;
	}
#endif

#ifdef DEBUG
	fprintf(stderr,"Generating checkpoints\n");
#endif
	// ważne punkty
	for(int i=1;i<=NumberOfQueries();++i) {
		q[QueryFrom(i)]=-1;
		q[QueryTo(i)]=-1;
	}
	// punkty kontrolne
	for(int i=1;i<=NumberOfStudents();i+=20000000) {
		q[i]=-1;
	}
	for(int i=144;i<=NumberOfStudents();i+=10007000) {
		q[i]=-1;
	}
	
	if(MyNodeId()!=0) {	// pracownik
		for(;;) {
#ifdef DEBUG
			fprintf(stderr,"Waiting for command\n");
#endif
			Receive(0);
			int from=GetInt(0);
#ifdef DEBUG
			fprintf(stderr,"Command %d\n",from);
#endif
			if(from==-1) return 0;
			int dir=GetInt(0);
			Point p;
			if(dir>0) {
				p=walk(FirstNeighbor(from),from);
			} else {
				p=walk(SecondNeighbor(from),from);
			}
			PutInt(0,p.from);
			PutInt(0,p.to);
			PutInt(0,p.dist);
			PutInt(0,dir);
			Send(0);
#ifdef DEBUG
			fprintf(stderr,"Send response: %d -> %d = %d\n",p.from,p.to,p.dist);
#endif
		}
	}
	
	{
		queue<int> workers;
		for(int i=1;i<NumberOfNodes();++i) workers.push(i);
		
		for(map<int,int>::iterator i =q.begin();i!=q.end();++i) {
			for(int j=-1;j<2;j+=2) 
			{
				int worker;
				if(workers.size()>0) {
					worker=workers.front();
					workers.pop();
				} else {
#ifdef DEBUG
					fprintf(stderr,"Waiting for free worker\n");
#endif
					worker=Receive(-1);
					int from=GetInt(worker);
					int to=GetInt(worker);
					int dist=GetInt(worker);
					int dir=GetInt(worker);
					addPoint(from,to,dir,dist);
					addPoint(to,from,-dir,dist);
					//dat[p1.from]=p1;
					//dat[p2.from]=p2;
				}
	#ifdef DEBUG
				fprintf(stderr,"Sending job request for: %d to %d\n",i->first,worker);
	#endif
				PutInt(worker,i->first);
				PutInt(worker,j);		// w dwie strony?
				Send(worker);
			}
		}
		// czekanie na wyniki
#ifdef DEBUG
		fprintf(stderr,"Waiting for jobs done\n");
#endif
		while(workers.size()+1<NumberOfNodes()) {
			int worker=Receive(-1);
			int from=GetInt(worker);
			int to=GetInt(worker);
			int dist=GetInt(worker);
			int dir=GetInt(worker);
			addPoint(from,to,dir,dist);
			addPoint(to,from,-dir,dist);
			workers.push(worker);
		}
#ifdef DEBUG
		fprintf(stderr,"Sending quit command\n");
#endif
		// wysłanie komunikatu zakończenia
		for(int i=1;i<NumberOfNodes();++i) {
			PutInt(i,-1);
			Send(i);
		}
#ifdef DEBUG
		fprintf(stderr,"Calculating results, %d points\n",dat.size());
		for(map<int,Point>::iterator i =dat.begin();i!=dat.end();++i) {
			fprintf(stderr,"Point %d -> %d = %d\n",i->second.from,i->second.to,i->second.dist);
			fprintf(stderr,"Point %d -> %d = %d\n",i->second.from,i->second.to2,i->second.dist2);
		}

#endif
		//return 0;
		// obliczenie wyników na podtawie danych z mapy
		for(int i=1;i<=NumberOfQueries();++i) {
			int from=QueryFrom(i);
			int to=QueryTo(i);
			
			int dist1=mapWalk(from,to,1);
			int dist2=mapWalk(from,to,-1);

			printf("%d\n",min(dist1,dist2));
		}
	}
	
	return 0;
}