#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int UNDETERMINED = 0;
const int C_STATION = 1;
const int D_STATION = 2;
int N;
vector<int> station, type;
vector<vector<int>> G;
void solve_left(int c, int d, vector<int> candidates);
void solve_right(int c, int d, vector<int> candidates) {
if (candidates.size() <= 0) return;
int new_c = c, new_d = candidates.front();
for (auto i : candidates) {
if (i == c || i == d) continue;
if (G[c][i] < G[c][new_d]) new_d = i;
}
for (auto i : candidates) {
if (i == new_c || i == new_d) continue;
if (G[new_d][i] < G[new_d][new_c]) new_c = i;
}
vector<int> le, ri;
for (auto i : candidates) {
if (i == new_c || i == new_d) continue;
if (G[new_c][i] == G[new_d][i] + G[new_c][new_d]) le.push_back(i);
if (G[new_d][i] == G[new_c][i] + G[new_c][new_d]) ri.push_back(i);
}
type[new_c] = C_STATION;
type[new_d] = D_STATION;
station[new_d] = station[c] + G[c][new_d];
station[new_c] = station[new_d] - G[new_d][new_c];
// cerr << new_c << " " << new_d << "<-- right\n";
solve_left(new_c, new_d, le);
solve_right(new_c, new_d, ri);
}
void solve_left(int c, int d, vector<int> candidates) {
if (candidates.size() <= 0) return;
int new_d = d, new_c = candidates.front();
for (auto i : candidates) {
if (i == c || i == d) continue;
if (G[d][i] < G[d][new_c]) new_c = i;
}
for (auto i : candidates) {
if (i == new_c || i == new_d) continue;
if (G[new_c][i] < G[new_c][new_d]) new_d = i;
}
vector<int> le, ri;
for (auto i : candidates) {
if (i == new_c || i == new_d) continue;
if (G[new_d][i] == G[new_c][i] + G[new_c][new_d]) ri.push_back(i);
if (G[new_c][i] == G[new_d][i] + G[new_c][new_d]) le.push_back(i);
}
type[new_c] = C_STATION;
type[new_d] = D_STATION;
station[new_c] = station[d] - G[d][new_c];
station[new_d] = station[new_c] + G[new_d][new_c];
// cerr << new_c << " " << new_d << "<-- left\n";
solve_left(new_c, new_d, le);
solve_right(new_c, new_d, ri);
}
void findLocation(int N_, int first_, int location[], int stype[]) {
N = N_;
station.resize(N, -1), type.resize(N, UNDETERMINED);
G.assign(N, vector<int>(N, -1));
station[0] = first_;
type[0] = C_STATION;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (G[i][j] != -1) continue;
G[i][j] = G[j][i] = (i == j)? 0 : getDistance(i, j);
}
}
int d = 1;
for (int i = 0; i < N; i++) {
if (i == 0) continue;
if (G[0][d] > G[0][i]) d = i;
}
type[d] = D_STATION;
station[d] = station[0] + G[0][d];
int c = 0;
for (int i = 0; i < N; i++) {
if (i == d) continue;
if (G[d][c] > G[d][i]) c = i;
}
vector<int> le, ri;
for (int i = 0; i < N; i++) {
if (i == c || i == d) continue;
if (G[c][i] == G[d][i] + G[c][d]) le.push_back(i);
if (G[d][i] == G[c][i] + G[c][d]) ri.push_back(i);
}
type[c] = C_STATION;
station[c] = station[d] - G[c][d];
// cerr << c << " " << d << " step 0\n";
// le.push_back(d), ri.push_back(c);
solve_right(c, d, ri);
solve_left(c, d, le);
for (int i = 0; i < N; i++) stype[i] = type[i];
for (int i = 0; i < N; i++) location[i] = station[i];
// for (int i = 0; i < N; i++) cerr << type[i] << " ";
// cout << "\n";
// for (int i = 0; i < N; i++) cerr << station[i] << " ";
// cerr << "\n";
}
