#include "kollib.h"
#include "message.h"
#include <iostream>
#include <set>
#include <vector>
#include <stdio.h>
#include <string.h>

using namespace std;
#define CL(a,x) 		memset(a,x,sizeof(a))
#define MP 		make_pair

typedef pair<int,int>     pii; 
typedef vector<pii> vii;
typedef vector<int>     vi;



int i,j,nd,id,z,c,k,b0,a2,b2,c2,g0,g2,i0;
int m,n,d,a,b,m0,a0,z2,a02,b02,bx,b2x;
int ta[500][500],tp[500],tp2[500];
pii p1,p2;
vii vq,va,vk1,vk2;
set <int> sq;
set<int>::iterator it;
vi vk,vk0;
vector<vii> vvk;

void pa(){
int i,j;
	for(i=0;i<m0;i++){
			for(j=0;j<m0;j++){
				cerr<<ta[i][j]<<" ";
			}
			cerr<<endl;
		}
		cerr<<endl;
}


int szu(int b){
	int i,i1,i2;

	i1=0;
	i2=m0-1;
	if(tp[i1]==b)
		return i1;
	if(tp[i2]==b)
		return i2;
	i=(i1+i2)/2;
	while(tp[i]!=b){
		if(tp[i]<b)
			i1=i;
		else
			i2=i;
		i=(i1+i2)/2;
	}
	return i;
}
int main() {

	nd=NumberOfNodes();
	n=NumberOfStudents();	
	id=MyNodeId();
	m=NumberOfQueries();
	CL(ta,0);
	CL(tp,0);
	CL(tp2,0);
	vq.clear();
	sq.clear();
	va.clear();
	
	//if(id==0)
		//cerr<<id<<" "<<nd<<" "<<n<<" "<<m<<endl;
	 for (i = 1; i <= m; ++i) {
		 a=QueryFrom(i);
		 b=QueryTo(i);
		// if(id==0)
		//	cerr<<a<<" "<<b<<endl;
		 vq.push_back(MP(a,b));
		if (a != b){
			if(sq.find(a)==sq.end())
				sq.insert(a);
			if(sq.find(b)==sq.end())
				sq.insert(b);
		}
	 }
	 i=0;
	 for (it=sq.begin(); it!=sq.end(); ++it)
		 tp[i++]=*it;
	 
	 
	m0=sq.size();
	vk.clear();
	vk0.clear();
	vvk.assign(m0,va);
	for(i=id;i<m0;i+=nd){
		vk.push_back(tp[i]);	//lista punktów startowych dla instancji id
		vk0.push_back(i);
	}

	for(i=0;i<vk.size();i++){
		//cerr<<"id= "<<id<<endl;
		a=vk[i];
		a2=a;
		a0=a;
		a02=a;
		g0=0;
		g2=0;
	//	cerr<<a<<endl;
	//	cerr<<b<<endl;
		b=FirstNeighbor(a);
		b2=SecondNeighbor(a);
		//if(id==0)
		//cerr<<a<<" "<<b<<" "<<b2<<endl;
		z=1;
		z2=1;
		while((sq.find(b)==sq.end())||(sq.find(b2)==sq.end())){
			if(sq.find(b)==sq.end()){
		//		cerr<<b<<endl;
				c=FirstNeighbor(b);
			//	if(id==0)
			//	cerr<<b<<" "<<c<<endl;
				if(c==a){
					c=SecondNeighbor(b);
			//		if(id==0)
			//		cerr<<b<<" "<<c<<endl;
				}
				a=b;
				b=c;
				z++;
			}
			
			if((g0==0)&&(sq.find(b)!=sq.end())){
				g0=1;
				b0=b;
				bx=szu(b);
				ta[vk0[i]][bx]=z;
				ta[bx][vk0[i]]=z;
				vvk[vk0[i]].push_back(MP(bx,z));
				vvk[bx].push_back(MP(vk0[i],z));
				tp2[bx]++;
				tp2[vk0[i]]++;
		
				if(id>0){				//wysyła komunikat do id=0:
										//od
										//do
										//z
					PutInt(0,a0);
					PutInt(0,b0);
					PutInt(0,z);
					Send(0);
				//	cerr<<"send"<<a0<<" "<<b0<<" "<<z<<endl;
				}
			}
			
			if(sq.find(b2)==sq.end()){
			//	cerr<<b2<<endl;
				c2=FirstNeighbor(b2);
			//	if(id==0)
			//	cerr<<b2<<" "<<c2<<endl;
				if(c2==a2){
					c2=SecondNeighbor(b2);
			//		if(id==0)
			//		cerr<<b2<<" "<<c2<<endl;
				}
				a2=b2;
				b2=c2;
				z2++;
			}
			
			if((g2==0)&&(sq.find(b2)!=sq.end())){
				g2=1;
				b02=b2;
				b2x=szu(b2);
				ta[vk0[i]][b2x]=z2;
				ta[b2x][vk0[i]]=z2;
				vvk[vk0[i]].push_back(MP(b2x,z2));
				vvk[b2x].push_back(MP(vk0[i],z2));
				tp2[b2x]++;
				tp2[vk0[i]]++;
				if(id>0){				//wysyła komunikat do id=0:
										//od
										//do
										//z
					PutInt(0,a02);
					PutInt(0,b02);
					PutInt(0,z2);
					Send(0);
				//	cerr<<"send"<<a02<<" "<<b02<<" "<<z2<<endl;
				//	cerr<<"ivk "<<i<<" "<<vk.size()<<endl;
				}
			}
			

		}
		
		
	}
	if(id==0){
		
	
		k=0;
		for(i=0;i<m0;i++)
			k+=tp2[i];
		cerr<<"k0 = "<<k<<endl;
		while(k<4*(m0-1)){
		//	cerr<<"k = "<<k<<endl;
			j=Receive(-1);
			
			a=GetInt(j);
			b=GetInt(j);
			z=GetInt(j);
			cerr<<"receive"<<a<<" "<<b<<" "<<z<<endl;
			a=szu(a);
			b=szu(b);
			ta[a][b]=z;
			ta[b][a]=z;
			tp2[b]++;
			tp2[a]++;
			k+=2;
			
		}
		/*
		for(i=0;i<m0;i++){
			for(j=0;j<m0;j++){
				cerr<<ta[i][j]<<" ";
			}
			cerr<<endl;
		}
		cerr<<endl;
*/
		/*
		for(i=0;i<m0;i++){
			for(j=0;j<vvk[i].size();j++){
				cerr<<vvk[i][j].first<<" ";
			}
			cerr<<endl;
		}
		*/
		
		for(i=0;i<m0;i++){
			for(j=0;j<m0;j++){
				if(ta[i][j]!=0){
					for(int i1=0;i1<m0;i1++){
						if(i!=i1){
							if(ta[i][i1]!=0){
								if(ta[j][i1]==0){
									ta[j][i1]=ta[j][i]+ta[i][i1];
									ta[i1][j]=ta[j][i1];
								}
								else if(ta[j][i1]>ta[j][i]+ta[i][i1]){
									ta[j][i1]=ta[j][i]+ta[i][i1];
									ta[i1][j]=ta[j][i1];
								}
							}
						}
					}
				}
			}
		}
						
		z=-1;
		for(i=0;i<m0;i++){
			for(j=i+1;j<m0;j++){
				
				if(ta[i][j]==0){
					z=0;
					
					for(int i2=0;i2<m0-1;i2++){
						a=n+1;
						for(int i1=0;i1<m0;i1++){
							if(i1!=i&&i1!=j){
								a=min(a,ta[i][i1]);
								i0=i1;
							}
						}
						z+=a;
						i=i0;
					}
					ta[i][j]=z;
					ta[j][i]=z;
				}
				if(z>=0)
					break;
			}
			if(z>=0)
				break;
		}
							
									
		for(i=0;i<vq.size();i++){
			p1=vq[i];
		//	cerr<<p1.first<<p1.second<<endl;
			if(p1.first==p1.second)
				cout<<0<<endl;
			else {
				p2=p1;
				p1.first=szu(p1.first);
				p1.second=szu(p1.second);
				if(ta[p1.first][p1.second]==0){
					vk1=vvk[p1.first];
					vk2.clear();
					while(vk1.size()>0){
						//cerr<<"size = "<<vk1.size()<<endl;
						for(int ix=0;ix<vk1.size();ix++){
							a=vk1[ix].first;
							z=vk1[ix].second;
							//cerr<<a<<endl;
							for(j=0;j<vvk[a].size();j++){
								if(ta[p1.first][vvk[a][j].first]==0){
									ta[p1.first][vvk[a][j].first]=z+vvk[a][j].second;
									ta[vvk[a][j].first][p1.first]=z+vvk[a][j].second;
									vk2.push_back(MP(vvk[a][j].first,z+vvk[a][j].second));
								}
								else if(ta[p1.first][vvk[a][j].first]>z+vvk[a][j].second) {
									ta[p1.first][vvk[a][j].first]=z+vvk[a][j].second;
									ta[vvk[a][j].first][p1.first]=z+vvk[a][j].second;
									vk2.push_back(MP(vvk[a][j].first,z+vvk[a][j].second));
								}
								
							}
						}
						//cerr<<"vk2 = "<<vk2.size()<<endl;
						//if(ta[p1.first][p1.second]!=0)
						//	break;
						swap(vk1,vk2);
						vk2.clear();
					}
				}
						
				
				cout<<ta[p1.first][p1.second]<<endl;
			//	pa();
			}
		}

	}
	
  
  return 0;
}