#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <ctime>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PI;
typedef unordered_map<int,int> hashset;
#define MP make_pair
#define PB push_back
#define SD second
#define FT first

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

int k,n,m,q;
int ja;

const int N = 203;
const int INF = 20000000;
const int MADRYOD = 10003;

vector<PI> zapytania;
int odpowiedzi[N];
int zrobiono;

void WyslijZadanie(int maszyna, int numerZadania, int z, int dok) 
{
	PutInt(maszyna, numerZadania);
	PutInt(maszyna, z);
	PutInt(maszyna, dok);
	Send(maszyna);
}

void Fajrant(int maszyna) 
{
	PutInt(maszyna, -666);
	Send(maszyna);
}

int OdbierzWynik(int &numerMaszyny, int &zadanie, int &wynik) {
	numerMaszyny = Receive(-1);
	zadanie = GetInt(numerMaszyny);
	wynik = GetInt(numerMaszyny);
	return true;
}

void gogoSzefMadry();
void gogoSzef() {
	if(n > MADRYOD) {
		gogoSzefMadry();
		return;
	}
		
	deque<int> oczekujaceZadania;
	deque<int> oczekujaceMaszyny;
	zrobiono = 0;
	for(int i=0;i<zapytania.size();i++) {
		oczekujaceZadania.PB(i);
	}
	for(int i=1;i<m;i++) {
		oczekujaceMaszyny.PB(i);
	}

	while(zrobiono<q) {
		while(oczekujaceZadania.size()>0&&oczekujaceMaszyny.size()>0) {
			int maszyna = oczekujaceMaszyny.front();
			int zadanie = oczekujaceZadania.front();
			oczekujaceMaszyny.pop_front();
			oczekujaceZadania.pop_front();
			WyslijZadanie(maszyna, zadanie, zapytania[zadanie].FT, zapytania[zadanie].SD);
		}
		int maszyna, numerZadania, wynik;
		if(OdbierzWynik(maszyna,numerZadania,wynik)) {
			odpowiedzi[numerZadania] = wynik;
			oczekujaceMaszyny.PB(maszyna);
			zrobiono++;
		}
	}
	
	for(int i=1;i<m;i++) 
		Fajrant(i);
	
	for(int i=0;i<q;i++) 
		printf("%d\n",odpowiedzi[i]);
}

int OdbierzZadanie(int &numer, int &z, int &dok) {
	Receive(0);
	numer = GetInt(0);
	if(numer == -666)
		return false;
	z = GetInt(0);
	dok = GetInt(0);
	return true;
}

int Sasiad(int numer, int ktory) {
	if(ktory==0) 
		return FirstNeighbor(numer+1)-1;
	else
		return SecondNeighbor(numer+1)-1;
}

void gogoPracownikMadry();
void gogoPracownik() 
{
	if(n > MADRYOD) {
		gogoPracownikMadry();
		return;
	}
    srand(time(NULL));
	int start, koniec, zadanie;
	while(OdbierzZadanie(zadanie,start,koniec)) {
		int kier = rand()%2;
		
		int res = -1;
		
		if(start == koniec) {
			res = 0;
		}
		else {
			int pop = start;
			int akt = Sasiad(start,kier);
			res = 1;
			while(akt!=koniec) {
				int sas=Sasiad(akt,kier);
				if(sas == pop) 
					sas = Sasiad(akt,!kier);
				res++;
				pop = akt;
				akt = sas;
			}
			res = min(res,n-res);
		}
		
		PutInt(0, zadanie);
		PutInt(0, res);
		Send(0);
	}
}


struct Odcinek {
	int a,b,c;
	int ab,bc;
	Odcinek() {
	
	}
	Odcinek(int _a, int _b, int _c, int _ab, int _bc) {
		a=_a;
		b=_b;
		c=_c;
		ab=_ab;
		bc=_bc;
	}
};

const int P = 450;
Odcinek odcinki[P+10];
int odcinkiZapytan[P+10];
bool wybrane[N];

int randomBig(int maks) {
	// TODO 
}

void WyslijZadanie2(int maszyna, int numer) 
{
	PutInt(maszyna, numer);
	Send(maszyna);
}

void WyslijInteresy(int maszyna, vector<int>&interesy) {
	PutInt(maszyna, interesy.size());
	for(int i=0;i<interesy.size();i++) 
		PutInt(maszyna, interesy[i]);
	Send(maszyna);
}

int OdbierzWynik2(int &numerMaszyny, int &zadanie, int &sl, int &sld, int &sp, int &spd) {
	numerMaszyny = Receive(-1);
	zadanie = GetInt(numerMaszyny);
	sl = GetInt(numerMaszyny);
	sld = GetInt(numerMaszyny);
	sp = GetInt(numerMaszyny);
	spd = GetInt(numerMaszyny);
	return true;
}



void gogoSzefMadry() {

	// Losuj dodatkowe punkty 
	// O(P)
	vector<PI> zapytaniaWInteresujacych;
	vector<int> interesujace;
	unordered_map<int,int> inside;
	for(int i=0;i<q;i++) {
		PI zi;
		if(inside.count(zapytania[i].FT) == 0) {
			zi.FT = interesujace.size();
			interesujace.PB(zapytania[i].FT);
			inside[zapytania[i].FT] = zi.FT;
		}
		else {
			zi.FT = inside[zapytania[i].FT];
		}
		if(inside.count(zapytania[i].SD) == 0) {
			zi.SD = interesujace.size();
			interesujace.PB(zapytania[i].SD);
			inside[zapytania[i].SD] = zi.SD;
		}
		else {
			zi.SD = inside[zapytania[i].SD];
		}
		zapytaniaWInteresujacych.PB(zi);
		//wybrane[zapytania[i].FT] = wybrane[zapytania[i].SD] = true;
	}
	srand(time(NULL));
	
	
	for(int i=q*2;i<P;i++) {
		int numer;
		if(RAND_MAX < 1000000000) {
			numer = (LL)((LL)rand()*RAND_MAX+rand())%n;
		}
		else numer = (LL)rand()%n;
		while(inside.count(numer)) {
			if(RAND_MAX < 1000000000) {
				numer = (LL)((LL)rand()*RAND_MAX+rand())%n;
			}
			else numer = (LL)rand()%n;
		}
		inside[numer] = interesujace.size();
		interesujace.PB(numer);
	}
	
	//printf("interesujace wygenerowane %d\n",P);
	
	for(int i=1;i<m;i++) 
		WyslijInteresy(i,interesujace);
	
	//printf("interesy wyslane %d\n",m);
	
	// wysyłaj do wszystkich wszystkich interesujących.
	// E[K] = N/P < 10^6
	// przydzielaj zadania szukania otoczenia kolejnych interesujących.
	
	deque<int> oczekujaceZadania;
	deque<int> oczekujaceMaszyny;
	zrobiono = 0;
	for(int i=0;i<interesujace.size();i++) {
		oczekujaceZadania.PB(i);
	}
	for(int i=1;i<m;i++) {
		oczekujaceMaszyny.PB(i);
	}
	
	while(zrobiono<interesujace.size()) {
		while(oczekujaceZadania.size()>0&&oczekujaceMaszyny.size()>0) {
			int maszyna = oczekujaceMaszyny.front();
			int zadanie = oczekujaceZadania.front();
			oczekujaceMaszyny.pop_front();
			oczekujaceZadania.pop_front();
			WyslijZadanie2(maszyna, zadanie);
		}
		int maszyna, numerZadania, wynikL,odlL,wynikP,odlP;
		// odbieraj wyliczone odcinki
		
		if(OdbierzWynik2(maszyna,numerZadania,wynikL,odlL,wynikP,odlP)) {
			//odpowiedzi[numerZadania] = wynik;
			//printf("mam wynik %d\n", numerZadania);
			//printf("odl %d %d \n", odlL,odlP);
			odcinki[numerZadania]=(Odcinek(wynikL,numerZadania,wynikP,odlL,odlP));
			/*if(wynikL == wynikP) {
				printf("DDDDDDDDDDUPA %d %d %d \n\n\n\n",wynikL,numerZadania,wynikP);
				return;
				}*/
			oczekujaceMaszyny.PB(maszyna);
			zrobiono++;
		}
	}
	
	//printf("zadania wykonane %d\n",m);
	
	for(int i=1;i<m;i++) 
		Fajrant(i);
	
	//printf("fajrant wykonane %d\n",m);
	
	
	// sklejaj odcinki w całość
	// O(P) - stawiaj pierwszego i doklejaj kolejnych
	vector<Odcinek> kolejnosc;
	kolejnosc.PB(odcinki[0]);
	while(kolejnosc.back().c!=kolejnosc.front().b) {
		//printf("start = %d, koniec = %d <- %d -> %d\n",kolejnosc.front().b,kolejnosc.back().a,kolejnosc.back().b,kolejnosc.back().c);
		int ost = kolejnosc.back().b;
		kolejnosc.PB(odcinki[kolejnosc.back().c]);
		if(kolejnosc.back().a != ost) {
			swap(kolejnosc.back().c,kolejnosc.back().a);
			swap(kolejnosc.back().bc,kolejnosc.back().ab);
		}
	}
	
	//printf("odcinki uporzadkowane %d\n",kolejnosc.size());

	// mając odleglości, szukaj wyniku
	// O(q * P) < 10^6
	for(int z=0;z<zapytaniaWInteresujacych.size();z++) {
		for(int k=0;k<kolejnosc.size();k++) {
			if(kolejnosc[k].b==zapytaniaWInteresujacych[z].FT) {
				int akt=k;
				int wartKon=zapytaniaWInteresujacych[z].SD;
				int res = 0;
				while(kolejnosc[akt].b!=wartKon) {
					res += kolejnosc[akt].bc;
					akt = (akt + 1)%P;
				}
				odpowiedzi[z] = min(res,n-res);
				break;
			}
		}
	}

	//printf("odpowiedzi przygotowane %d\n",zapytaniaWInteresujacych.size());
		
	for(int i=0;i<q;i++) 
		printf("%d\n",odpowiedzi[i]);
		
	// O(q * P + N/P) - zakładając ze mam P maszyn
	// baza - P = 1000
	// best - P = 2236
	// best = ( q - N/P^2 = 0 -> q * P^2 = N -> P = sqrt(N/q)) => wtedy czas to -> O(sqrt(N*q)) ~= sqrt(10^11 * 2) ~= 1,4 * 316000 ~=  442718
	// baza = 200 * 1000 + 10^6  = 1,2 * 10^6

	// O(q * P + N/M) - zakładając ze mam M maszyn oraz P > M  -> chcemy P == M , ale chcemy mieć równo podzielone
	// q * P == N/M -> P = N/M/q = 10^9/10^2/2/10^2 = 5*10^4 = 50000 -> P ===========> 500 (bo limit wiadomości)
	// baza - P = 1000
	// best = ( q - N/M^2 = 0 -> q * P^2 = N -> P = sqrt(N/q)) => wtedy czas to -> O(sqrt(N*q)) ~= sqrt(10^11 * 2) ~= 1,4 * 316000 ~=  442718
}

void OdbierzInteresy(hashset &interesy, vector<int> &interesyN) {
	Receive(0);
	int ile = GetInt(0);
	for(int i=0;i<ile;i++) {
		int wrat = GetInt(0); 
		interesy[wrat]=i;
		interesyN.PB(wrat);
	}
}

bool OdbierzZadanie2(int &numer) 
{
	Receive(0);
	numer = GetInt(0);
	return numer != -666;
}

void gogoPracownikMadry() {
	srand(time(NULL));
	int start, koniec, zadanie;
	
	hashset interesy;
	vector<int> interesyN;
	OdbierzInteresy(interesy,interesyN);
	
	while(OdbierzZadanie2(zadanie)) {
		Odcinek wynik;
		wynik.b=zadanie;
		wynik.ab=0;
		wynik.bc=0;
		
		int akt = Sasiad(interesyN[zadanie],0);

		//printf("L krok 2 %d %d\n", interesyN[zadanie], akt);
		int pop = interesyN[wynik.b];
		wynik.ab++;
		while(interesy.count(akt)==0) {
			int sas=Sasiad(akt,0);
			if(sas == pop) 
				sas = Sasiad(akt,1);
			pop = akt;
			akt = sas;
			wynik.ab++;
		}
		wynik.a=interesy[akt];
		
		akt = Sasiad(interesyN[zadanie],1);
		//printf("L krok 2 %d %d\n", interesyN[zadanie], akt);
		
		pop = interesyN[wynik.b];
		wynik.bc++;
		while(interesy.count(akt)==0) {
			int sas=Sasiad(akt,0);
			if(sas == pop) 
				sas = Sasiad(akt,1);
			pop = akt;
			akt = sas;
			wynik.bc++;
		}
		wynik.c=interesy[akt];
		
		
		
		PutInt(0, wynik.b);
		PutInt(0, wynik.a);
		PutInt(0, wynik.ab);
		PutInt(0, wynik.c);
		PutInt(0, wynik.bc);
		Send(0);
	}
}



int main() {
	n = NumberOfStudents();
	q = NumberOfQueries();
	for(int i=0;i<q;i++)
		zapytania.PB(MP(QueryFrom(i+1)-1, QueryTo(i+1)-1));
	m = NumberOfNodes();
	ja = MyNodeId();
	if(ja == 0) {
		gogoSzef();
		}
	else
		gogoPracownik();
	
	return 0;
}