#include "rail.h"
#include <iostream>
#include <vector>
using namespace std;
int dist[5009][5009], lm[5009], ln[5009]; vector<int>x[5009];
int getDist(int p, int q) {
if (p > q) swap(p, q);
if (p == q) return 0;
if (dist[p][q] != -1) return dist[p][q];
int z = getDistance(p, q); dist[p][q] = z;
return z;
}
int loc[5009], typ[5009];
void findLocation(int N, int first, int location[], int stype[]) {
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dist[i][j] = -1; }
int minx = (1 << 30), a1 = 0;
for (int i = 1; i < N; i++) { int r = getDist(0, i); if (r < minx) { minx = r; a1 = i; } }
for (int i = 0; i < N; i++) {
lm[i] = (1 << 30);
for (int j = 0; j < N; j++) {
if (i == j) continue;
int r = getDist(i, j);
if (r < lm[i]) { lm[i] = r; ln[i] = j; }
}
x[ln[i]].push_back(i);
}
vector<int>V; vector<pair<int, int>>W;
for (int i = 0; i < N; i++) {
if (x[i].size() >= 1) V.push_back(i);
}
for (int i = 0; i < V.size(); i++) {
for (int j = i + 1; j < V.size(); j++) {
if (ln[V[i]] == V[j] && ln[V[j]] == V[i]) W.push_back(make_pair(V[i], V[j]));
}
}
int a2 = 0;
for (int i = 0; i < W.size(); i++) {
if (W[i].first == a1) a2 = W[i].second;
if (W[i].second == a1) a2 = W[i].first;
}
for (int i = 0; i < W.size(); i++) {
if (W[i].first != 0 && getDist(a2, W[i].first) < getDist(a1, W[i].first)) {
// 右にある
if (getDist(W[i].first, 0) < getDist(W[i].second, 0)) swap(W[i].first, W[i].second);
loc[W[i].second] = getDist(W[i].second, 0);
loc[W[i].first] = loc[W[i].second] - getDist(W[i].first, W[i].second);
}
else {
// 左にある
if (W[i].second != a1 && getDist(W[i].first, a1) > getDist(W[i].second, a1)) swap(W[i].first, W[i].second);
if (W[i].first == a1) swap(W[i].first, W[i].second);
loc[W[i].first] = minx - getDist(W[i].first, a1);
loc[W[i].second] = loc[W[i].first] + getDist(W[i].first, W[i].second);
}
typ[W[i].first] = 1;
typ[W[i].second] = 2;
}
for (int i = 0; i < N; i++) {
if (x[i].size() >= 1) continue;
if (typ[ln[i]] == 2) {
typ[i] = 1;
loc[i] = loc[ln[i]] - getDist(i, ln[i]);
}
else {
typ[i] = 2;
loc[i] = loc[ln[i]] + getDist(ln[i], i);
}
}
for (int i = 0; i < N; i++) location[i] = loc[i] + first;
for (int i = 0; i < N; i++) stype[i] = typ[i];
return;
}
