1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
#include "message.h"
#include "kollib.h"
using namespace std;

set<int> S;
map<int,int> M;

int next(int i, int prev) {
	int x = FirstNeighbor(i);
	if(x != prev) return x;
	else return SecondNeighbor(i);
}

void sendPair(pair<int,int> p, int index) {
	PutInt(index, p.first);
	PutInt(index, p.second);
	Send(index);
}

pair<int,int> receivePair(int index) {
	Receive(index);
	int a = GetInt(index);
	int b = GetInt(index);
	return make_pair(a,b);
}

pair<int,int> find(int x, int prev) {
	int dist = 1;
	while(S.find(x) == S.end()) {
		int tmp = next(x, prev);
		prev = x;
		x = tmp;
		dist++;
	}
	return make_pair(x, dist);
}

struct node {
	int ptr1,ptr2,dist1,dist2;
	node() : ptr1(-1), ptr2(-1) {}
	void setNext(int x, int dist);
	int getNext(int prev) {
		if(ptr1 == prev) return ptr2;
		else return ptr1;
	}
} N[505];


void node::setNext(int x, int dist) {
	if(ptr1 == -1) {
		ptr1 = x;
		dist1 = dist;
	} 
	else if(ptr2 == -1) {
		ptr2 = x;
		dist2 = dist;
	}
}


int query(int a, int b, bool x) {
	int first = a;
	int i;
	if(x) i = N[M[first]].ptr1;
	else i = N[M[first]].ptr2;
	int prev = first;
	
	int res;
	if(x) res = N[M[first]].dist1;
	else res = N[M[first]].dist2;
	
	while(i != b) {
		int tmp = N[M[i]].getNext(prev);
		res += (N[M[i]].ptr1 == prev) ? (N[M[i]].dist2) : (N[M[i]].dist1);
		prev = i;
		i = tmp;
	}
	return res;
}

int main() 
{
	int n = NumberOfQueries();
	for(int i=1;i<=n;i++) {
		S.insert( QueryFrom(i) );
		S.insert( QueryTo(i) )	;
	}
	
	int nodes = NumberOfNodes();
	int id = MyNodeId();
	int i = 0;
	
	for(set<int>::iterator it=S.begin(); it!=S.end(); ++it, i++) {
		if((i % nodes) == id) {
			pair<int,int> p1 = find(FirstNeighbor(*it), *it);
			pair<int,int> p2 = find(SecondNeighbor(*it), *it);
			sendPair(p1,0);
			sendPair(p2,0);
		}
	}
	
	if(id == 0) {
		int i = 0;
		for(set<int>::iterator it=S.begin(); it!=S.end(); ++it, i++) M.insert(make_pair(*it,i));
		i = 0;
		for(set<int>::iterator it=S.begin(); it!=S.end(); ++it, i++) {
			pair<int,int> p1 = receivePair(i % nodes);
			//printf("%d %d %d\n",*it,p1.first,p1.second);
			N[M[*it]].setNext(p1.first, p1.second);
			pair<int,int> p2 = receivePair(i % nodes);
			//printf("%d %d %d\n",*it,p2.first,p2.second);
			N[M[*it]].setNext(p2.first, p2.second);
		}
		
		for(int i=1;i<=n;i++) {
			int a = QueryFrom(i);
			int b = QueryTo(i);
			//printf("%d %d %d %d\n",QueryFrom(i),QueryTo(i),query(a,b,true),query(a,b,false));
			if(a == b) printf("0\n");
			else printf("%d\n",min(query(a,b,true), query(a,b,false)));
		}
		
		//for(int i=0;i<10;i++) printf("%d %d %d\n",i,N[i].ptr1,N[i].ptr2);
	}
	
	return 0;
}