//Jakub Staroñ
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <random>
#include "message.h"
#include "kollib.h"

std::knuth_b random_generator(1002 ^ NumberOfNodes());

#ifdef COMPILING_HOME
#define DEBUG_MODE
#define HAVE_NEW_STANDARD
#endif

#ifdef HAVE_NEW_STANDARD
#include <unordered_map>
#include <unordered_set>
#else
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace std::tr1;
#endif

#define hash_map      unordered_map
#define hash_multimap unordered_multimap
#define hash_set      unordered_set
#define hash_multiset unordered_multiset

using namespace std;

typedef char int8;
typedef unsigned char uint8;
typedef short int int16;
typedef unsigned short int uint16;
typedef int int32;
typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;

typedef std::pair<int32,int32> int32_pair;
typedef std::pair<uint32, uint32> uint32_pair;
typedef std::pair<int64,int64> int64_pair;
typedef std::pair<uint64,uint64> uint64_pair;

typedef std::vector<bool> bit_vector;

#ifdef HAVE_NEW_STANDARD
#define let(a,b) auto a = (b)
#else
#define let(a,b) __typeof (b) a = (b)
#endif

#ifdef DEBUG_MODE
#define pause system("pause")
#define clear_screen system("cls")
#define print(x) cerr << #x << " = " << x << endl
#define label_print(label, value) cerr << label << ' ' << value << endl
#define debug(x) x
#define line cerr << "Line " << __LINE__ << endl
#include <cassert>
#else
#define pause
#define clear_screen
#define print(x)
#define label_print(label, value)
#define debug(x)
#define assert(x)
#define line
#endif

#define rep(i,x) for(uint32 i = 0 ; i < (x) ; i++)
#define for_range(i,begin,end) for( let(i, (begin) ) ; i != (end) ; ++i )
#define foreach(i, c) for_range(i, c.begin(), c.end())
#define abs(a) ( (a) < 0 ? -(a) : (a) )
#define all(c) (c).begin(),(c).end()
#define sort_all(x) sort( all(x) )
#define divide(a,b) ( ( (b)%(a) ) == 0 )
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)

#define min(a,b) ( (a) < (b)? (a) : (b) )
#define max(a,b) ( (a) > (b)? (a) : (b) )
#define min3(a,b,c) (  min((a), min((b),(c))) )
#define max3(a,b,c) (  max((a), max((b),(c))) )
#define sig(x) ( (x) == 0 ? 0 : ( (x) < 0 ? -1 : 1 ) )

const double epsilon = 1e-5;

template<class T>
void unique(std::vector<T>& v)
{
	sort_all(v);
	v.resize( std::unique(all(v)) - v.begin() );
}

ostream& newline(ostream& str)
{
	str.put('\n');
	return str;
}

template<typename T1, typename T2>
istream& operator>>(istream& stream, std::pair<T1, T2>& pair)
{
	stream >> pair.first >> pair.second;
	return stream;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& stream, const std::pair<T1, T2>& pair)
{
#ifdef DEBUG_MODE
	stream << "(" << pair.first << ", " << pair.second << ")";
#else
	stream << pair.first << ' ' << pair.second;
#endif
	return stream;
}

class Graf
{
public:
	typedef map<uint32, uint32> list_type;

	void add(uint32 a, uint32 b, uint32 c)
	{
		graf[a][b] = c;
		graf[b][a] = c;
	}

	list_type& obok(uint32 k)
	{
		return graf[k];
	}

	uint32 size()
	{
		return graf.size();
	}

private:
	map<uint32, list_type> graf;
};

class Application
{
public:
	Application()
	{
		Nodes = NumberOfNodes();
		N = NumberOfStudents();
		M = NumberOfQueries();
		ID = MyNodeId();
	}

	void Run()
	{
		if(N <= 100000)
		{
			if(ID == 0)
			{
				Small();
			}
		}
		else
		{
			Big();
		}
	}

	void Small()
	{
		vector<uint32> cycle;
		cycle.pb(0);
		cycle.pb( first(0) );

		while(cycle.back() != 0)
		{
			uint32 ten = cycle.back();
			uint32 prev = cycle[ cycle.size() - 2 ];
			cycle.pb( next(ten, prev) );
		}

		cycle.pop_back();

		vector<int32> position(N);
		rep(i, N)
		{
			position[ cycle[i] ] = i;
		}

		rep(i, M)
		{
			int32_pair query = get_query(i);

			uint32 dist = abs( position[query.first] - position[query.second] );

			cout << min(dist, N - dist) << newline;
		}
	}

	void Big()
	{
		if(ID == 0)
		{
			Master();
		}
		else
		{
			Slave();
		}
	}

	void Master()
	{
		//przydzielamy poczatki
		vector<uint32> start(Nodes);
		for_range(i, 1, Nodes)
		{
			uint32 next_node = random_generator() % N;
			while(global.count(next_node))
			{
				next_node = random_generator() % N;
			}
			start[i] = next_node;
			global.insert(next_node);
		}

		for_range(i, 1, Nodes)
		{
			//wysyłamy poczatki
			for_range(j, 1, Nodes)
			{
				PutInt(i, start[j]);
			}
			Send(i);
		}


		uint32 exits = 0;
		while(exits < Nodes - 1)
		{
			int32 from_id = Receive(-1);
			char c = GetChar(from_id);

			if(c == 'e')
			{
				exits++;
			}
			else
			{
				uint32 a = GetInt(from_id);
				uint32 b = GetInt(from_id);
				uint32 c = GetInt(from_id);

				graf.add(a,b,c);
			}
		}

		rep(i, M)
		{
			int32 result = Dist(get_query(i));
			cout << min(result, N - result) << newline;
		}		
	}

	int32 Dist(int32_pair query)
	{
		set<uint32> odwiedzone;
		map<int32, int32> dist;

		priority_queue< uint32_pair, std::vector<uint32_pair>, std::greater<uint32_pair> > Q;

		uint32 start = query.first;
		dist[start] = 0;
		Q.push( mp(0, start) );

		while(!Q.empty())
		{
			uint32_pair p = Q.top();
			Q.pop();

			uint32 v = p.second;
			uint32 d = p.first;

			if(!odwiedzone.count(v))
			{
				continue;
			}

			for(int32_pair u : graf.obok(v))
			{
				uint32 new_dist = d + u.second;

				if(dist.count(u.first) == 0 || dist[u.first] > new_dist)
				{
					dist[u.first] = new_dist;	
					Q.push( mp(dist[u.first], u.first) );
				}
			}

			odwiedzone.insert(v);
		}

		if(dist.count(query.second) > 0)
		{
			return dist[query.second];
		}
		else
		{
			return -1;
		}
	}

	void Slave()
	{
		//odbieramy poczatki przeszukiwan
		Receive(0);

		
		for_range(i, 1, Nodes)
		{
			uint32 start_of = GetInt(0);
			global.insert(start_of);

			if(i == ID)
				my_start = start_of;
		}

		//pzeszukujemy sasiedztwo
		InitializeLocal();

		send_distance(my_start, skrajne_osoby.first);
		send_distance(my_start, skrajne_osoby.second);		

		rep(i, M)
		{
			int32_pair query = get_query(i);

			
			if(local.count(query.first) > 0)
				send_inner_distance(query.first);

			if(local.count(query.second) > 0)
				send_inner_distance(query.second);

		}	

		PutChar(0, 'e');
		Send(0);
	}

	void send_inner_distance(uint32 a)
	{
		send_distance(my_start, a);
		send_distance(skrajne_osoby.first, a);
		send_distance(skrajne_osoby.second, a);
	}

	void send_distance(uint32 a, uint32 b)
	{
		PutChar(0, 'a');
		PutInt(0, a);
		PutInt(0, b);
		int32 dist = abs(local[a] - local[b]);
		PutInt(0, dist );
		Send(0);
	}

	

	void InitializeLocal()
	{
		local[my_start] = 0;

		{
			int32 index = 1;

			uint32 y = my_start;
			uint32 x = first(my_start);

			while(global.count(x) == 0)
			{
				local[x] = index++;

				uint32 tmp = x;
				x = next(x, y);
				y = tmp;
			}
			local[x] = index;

			skrajne_osoby.first = x;
		}

		{
			int32 index = -1;

			uint32 y = my_start;
			uint32 x = second(my_start);

			while(global.count(x) == 0)
			{
				local[x] = index--;
				
				uint32 tmp = x;
				x = next(x, y);
				y = tmp;
			}
			local[x] = index;

			skrajne_osoby.second = x;
		}
	}

	int32_pair get_query(uint32 id)
	{
		return int32_pair( QueryFrom(id + 1) - 1, QueryTo(id + 1) - 1 );
	}

	uint32 next(uint32 ten, uint32 prev)
	{
		uint32 a = first(ten);
		if(a == prev)
		{
			return second(ten);
		}
		else
		{
			return a;
		}	
	}

	uint32 first(uint32 n)
	{
		return FirstNeighbor(n + 1) - 1;
	}

	uint32 second(uint32 n)
	{
		return SecondNeighbor(n + 1) - 1;
	}
	

	uint32 Nodes, N, M, ID;

	set<uint32> global;
	map<uint32, int32> local;

	int32_pair skrajne_osoby;

	Graf graf;

	uint32 my_start;
};


int main()
{
	ios::sync_with_stdio(0);
	Application application;
	application.Run();
	return 0;
}