sphinx (IOI contest)
Time limit: 1.5 seconds | Memory limit: 2048 MB | Task type: interactive
Algorithms: graph theory, union-find, data structures, binary search, implementation, constructive

# Sphinx's Riddle

The Great Sphinx has a riddle for you. 
You are given a graph on $N$ vertices.
The vertices are numbered from $0$ to $N - 1$.
There are $M$ edges in the graph, numbered from $0$ to $M-1$.
Each edge connects a pair of distinct vertices and is bidirectional.
Specifically, for each $j$ from $0$ to $M - 1$ (inclusive)
 edge $j$ connects vertices $X[j]$ and $Y[j]$.
There is at most one edge connecting any pair of vertices.
Two vertices are called **adjacent**
 if they are connected by an edge.

A sequence of vertices $v_0, v_1, \ldots, v_k$ (for $k \ge 0$)
 is called a **path**
 if each two consecutive vertices $v_l$ and $v_{l+1}$
 (for each $l$ such that $0 \le l \lt k$)
 are adjacent.
We say that a path $v_0, v_1, \ldots, v_k$ **connects** vertices $v_0$ and $v_k$.
In the graph given to you, each pair of vertices is connected by some path.

There are $N + 1$ colours, numbered from $0$ to $N$.
Colour $N$ is special and is called the **Sphinx's colour**.
Each vertex is assigned a colour.
Specifically, vertex $i$ ($0 \le i \lt N$) has colour $C[i]$.
Multiple vertices may have the same colour, 
and there might be colours not assigned to any vertex.
No vertex has the Sphinx's colour,
 that is, $0 \le C[i] \lt N$ ($0 \le i \lt N$).

A path $v_0, v_1, \ldots, v_k$ (for $k \ge 0$)
 is called **monochromatic**
 if
 all of its vertices have the same colour,
 i.e. $C[v_l] = C[v_{l+1}]$ (for each $l$ such that $0 \le l \lt k$).
Additionally, we say that vertices $p$ and $q$ ($0 \le p \lt N$, $0 \le q \lt N$)
 are in the same **monochromatic component**
 if and only if they are connected by a monochromatic path.

You know the vertices and edges,
 but you do not know which colour each vertex has.
You want to find out the colours of the vertices,
 by performing **recolouring experiments**.

In a recolouring experiment,
 you may recolour arbitrarily many vertices.
Specifically, to perform a recolouring experiment
 you first choose an array $E$ of size $N$,
 where for each $i$ ($0 \le i \lt N$),
 $E[i]$ is between $-1$ and $N$ **inclusive**.
Then, the colour of each vertex $i$ becomes $S[i]$, where the value of $S[i]$ is:
* $C[i]$, that is, the original colour of $i$, if $E[i] = -1$, or
* $E[i]$, otherwise.

Note that this means that you can use the Sphinx's colour in your recolouring.

Finally, the Great Sphinx announces
 the number of monochromatic components in the graph,
 after setting the colour of each vertex $i$ to $S[i]$ ($0 \le i \lt N$).
The new colouring is applied only for this particular recolouring experiment,
 so **the colours of all vertices return to the original ones after the experiment finishes**.

Your task is to identify the colours of the vertices in the graph
 by performing at most $2\,750$ recolouring experiments. 
You may also receive a partial score
 if you correctly determine for every pair of adjacent vertices,
 whether they have the same colour.

## Implementation Details

You should implement the following procedure.

```
std::vector&lt;int&gt; find_colours(int N,
    std::vector&lt;int&gt; X, std::vector&lt;int&gt; Y)
```

* $N$: the number of vertices in the graph.
* $X$, $Y$: arrays of length $M$ describing the edges.
* This procedure should return an array $G$ of length $N$,
   representing the colours of vertices in the graph.
* This procedure is called exactly once for each test case.

The above procedure can make calls to the following procedure
 to perform recolouring experiments:

```
int perform_experiment(std::vector&lt;int&gt; E)
```

* $E$: an array of length $N$ specifying how vertices should be recoloured.
* This procedure returns the number of monochromatic components
   after recolouring the vertices according to $E$.
* This procedure can be called at most $2\,750$ times.

The grader is **not adaptive**, that is,
 the colours of the vertices are fixed before a call to `find_colours` is made.

## Constraints

* $2 \le N \le 250$
* $N - 1 \le M \le \frac{N \cdot (N - 1)}{2}$
* $0 \le X[j] \lt Y[j] \lt N$ for each $j$ such that $0 \le j \lt M$.
* $X[j] \neq X[k]$ or $Y[j] \neq Y[k]$
   for each $j$ and $k$ such that $0 \le j \lt k \lt M$.
* Each pair of vertices is connected by some path.
* $0 \le C[i] \lt N$ for each $i$ such that $0 \le i \lt N$.

## Subtasks

| Subtask | Score  | Additional Constraints |
| :-----: | :----: | ---------------------- |
| 1       | $3$    | $N = 2$
| 2       | $7$    | $N \le 50$
| 3       | $33$   | The graph is a path: $M = N - 1$ and vertices $j$ and $j+1$ are adjacent ($0 \leq j < M$).
| 4       | $21$   | The graph is complete: $M = \frac{N \cdot (N - 1)}{2}$ and any two vertices are adjacent.
| 5       | $36$   | No additional constraints.

In each subtask, you can obtain a partial score
 if your program determines correctly
 for every pair of adjacent vertices
 whether they have the same colour.

More precisely,
 you get the whole score of a subtask
 if in all of its test cases,
 the array $G$ returned by `find_colours`
 is exactly the same as array $C$
 (i.e. $G[i] = C[i]$
 for all $i$ such that $0 \le i \lt N$).
Otherwise,
 you get $50\%$ of the score for a subtask
 if the following conditions hold
 in all of its test cases:
* $0 \le G[i] \lt N$
   for each $i$ such that $0 \le i \lt N$;
* For each $j$ such that $0 \le j \lt M$:
  * $G[X[j]] = G[Y[j]]$ if and only if $C[X[j]] = C[Y[j]]$.

## Example

Consider the following call.

```
find_colours(4, [0, 1, 0, 0], [1, 2, 2, 3])
```

For this example, suppose that
 the (hidden) colours of the vertices are given by
 $C = [2, 0, 0, 0]$.
This scenario is shown in the following figure.
Colours are additionally represented by numbers on white labels attached to each vertex.

![example.png](sphinx_example.png "230")

The procedure may call `perform_experiment` as follows.

```
perform_experiment([-1, -1, -1, -1])
```

In this call, no vertex is recoloured, as all vertices keep their original colours.

Consider vertex $1$ and vertex $2$.
They both have colour $0$ and the path $1, 2$ is a monochromatic path.
As a result, vertices $1$ and $2$ are in the same monochromatic component.

Consider vertex $1$ and vertex $3$.
Even though both of them have colour $0$,
 they are in different monochromatic components
 as there is no monochromatic path connecting them.

Overall, there are $3$ monochromatic components,
 with vertices $\{0\}$, $\{1, 2\}$, and $\{3\}$.
Thus, this call returns $3$.

Now the procedure may call `perform_experiment` as follows.

```
perform_experiment([0, -1, -1, -1])
```

In this call, only vertex $0$ is recoloured to colour $0$,
 which results in the colouring shown in the following figure.

![example.png](sphinx_order1.png "230")

This call returns $1$, as all the vertices belong to the same monochromatic component.
We can now deduce that vertices $1$, $2$, and $3$ have colour $0$.

The procedure may then call `perform_experiment` as follows.

```
perform_experiment([-1, -1, -1, 2])
```

In this call, vertex $3$ is recoloured to colour $2$,
 which results in the colouring shown in the following figure.

![example.png](sphinx_order2.png "230")

This call returns $2$, as there are $2$ monochromatic components,
 with vertices $\{0, 3\}$ and $\{1, 2\}$ respectively. 
We can deduce that vertex $0$ has colour $2$.

The procedure `find_colours` then returns the array $[2, 0, 0, 0]$.
Since $C = [2, 0, 0, 0]$, full score is given.

Note that there are also multiple return values, for which $50\%$ of the score would be given, for example $[1, 2, 2, 2]$ or $[1, 2, 2, 3]$.

## Sample Grader

Input format:

```
N  M
C[0]  C[1] ... C[N-1]
X[0]  Y[0]
X[1]  Y[1]
...
X[M-1]  Y[M-1]
```

Output format:

```
L  Q
G[0]  G[1] ... G[L-1]
```

Here, $L$ is the length of the array $G$ returned by `find_colours`,
 and $Q$ is the number of calls to `perform_experiment`.


Starter code:
grader.cpp: #include "sphinx.h"
#include <cassert>
#include <cstdio>
#include <queue>
#include <string>
#include <vector>

namespace {

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

int N, M;
std::vector<int> C;
std::vector<int> X, Y;
std::vector<std::vector<int>> adj;

void quit(const char* message) {
  printf("%s\n", message);
  exit(0);
}

int count_components(const std::vector<int>& S) {
  int components_cnt = 0;
  std::vector<bool> vis(N, false);
  for (int i = 0; i < N; i++) {
    if (vis[i])
      continue;
    components_cnt++;

    std::queue<int> q;
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int nxt : adj[cur])
        if (!vis[nxt] && S[nxt] == S[cur]) {
          vis[nxt] = true;
          q.push(nxt);
        }
    }
  }
  return components_cnt;
}

} // namespace

int perform_experiment(std::vector<int> E) {
  calls_cnt++;
  if (calls_cnt > CALLS_CNT_LIMIT)
    quit("Too many calls");
  if ((int)E.size() != N)
    quit("Invalid argument");
  for (int i = 0; i < N; i++)
    if (!(-1 <= E[i] && E[i] <= N))
      quit("Invalid argument");

  std::vector<int> S(N);
  for (int i = 0; i < N; i++)
    S[i] = (E[i] == -1 ? C[i] : E[i]);

  return count_components(S);
}

int main() {
  assert(2 == scanf("%d%d", &N, &M));
  C.resize(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &C[i]));
  X.resize(M), Y.resize(M);
  for (int j = 0; j < M; j++)
    assert(2 == scanf("%d%d", &X[j], &Y[j]));
  fclose(stdin);

  adj.assign(N, std::vector<int>());
  for (int j = 0; j < M; j++) {
    adj[X[j]].push_back(Y[j]);
    adj[Y[j]].push_back(X[j]);
  }

  calls_cnt = 0;
  std::vector<int> G = find_colours(N, X, Y);

  int L = G.size();
  printf("%d %d\n", L, calls_cnt);
  for (int i = 0; i < L; i++)
    printf("%s%d", (i == 0 ? "" : " "), G[i]);
  printf("\n");
  fclose(stdout);

  return 0;
}

sphinx.h: #include <vector>

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y);

int perform_experiment(std::vector<int> E);

sphinx.cpp: #include "sphinx.h"

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  std::vector<int> E(N, -1);
  int x = perform_experiment(E);
  std::vector<int> G(N, 0);
  if (x == 1)
    G[0] = 1;
  return G;
}


Grader code:
grader.cpp: #include "sphinx.h"
#include <cassert>
#include <cstdio>
#include <queue>
#include <string>
#include <vector>

namespace {

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

int N, M;
std::vector<int> C;
std::vector<int> X, Y;
std::vector<std::vector<int>> adj;

void quit(const char* message) {
  printf("%s\n", message);
  exit(0);
}

int count_components(const std::vector<int>& S) {
  int components_cnt = 0;
  std::vector<bool> vis(N, false);
  for (int i = 0; i < N; i++) {
    if (vis[i])
      continue;
    components_cnt++;

    std::queue<int> q;
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int nxt : adj[cur])
        if (!vis[nxt] && S[nxt] == S[cur]) {
          vis[nxt] = true;
          q.push(nxt);
        }
    }
  }
  return components_cnt;
}

} // namespace

int perform_experiment(std::vector<int> E) {
  calls_cnt++;
  if (calls_cnt > CALLS_CNT_LIMIT)
    quit("Too many calls");
  if ((int)E.size() != N)
    quit("Invalid argument");
  for (int i = 0; i < N; i++)
    if (!(-1 <= E[i] && E[i] <= N))
      quit("Invalid argument");

  std::vector<int> S(N);
  for (int i = 0; i < N; i++)
    S[i] = (E[i] == -1 ? C[i] : E[i]);

  return count_components(S);
}

int main() {
  assert(2 == scanf("%d%d", &N, &M));
  C.resize(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &C[i]));
  X.resize(M), Y.resize(M);
  for (int j = 0; j < M; j++)
    assert(2 == scanf("%d%d", &X[j], &Y[j]));
  fclose(stdin);

  adj.assign(N, std::vector<int>());
  for (int j = 0; j < M; j++) {
    adj[X[j]].push_back(Y[j]);
    adj[Y[j]].push_back(X[j]);
  }

  calls_cnt = 0;
  std::vector<int> G = find_colours(N, X, Y);

  int L = G.size();
  printf("%d %d\n", L, calls_cnt);
  for (int i = 0; i < L; i++)
    printf("%s%d", (i == 0 ? "" : " "), G[i]);
  printf("\n");
  fclose(stdout);

  return 0;
}

sphinx.h: #include <vector>

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y);

int perform_experiment(std::vector<int> E);

manager.cpp: #include "testlib.h"
#include <algorithm>
#include <cassert>
#include <csignal>
#include <cstdio>
#include <memory>
#include <queue>
#include <string>
#include <vector>

using namespace std;

/******************************** Begin testlib-related material ********************************/

inline FILE* openFile(const char* name, const char* mode) {
	FILE* file = fopen(name, mode);
	if (!file)
		quitf(_fail, "Could not open file '%s' with mode '%s'.", name, mode);
	closeOnHalt(file);
	return file;
}


vector<FILE*> mgr2sol, sol2mgr;
FILE* log_file = nullptr;

void nullifyFile(int idx) {
	mgr2sol[idx] = sol2mgr[idx] = nullptr;
}

#ifdef __GNUC__
__attribute__ ((format (printf, 1, 2)))
#endif
void log_printf(const char* fmt, ...) {
	if (log_file) {
		FMT_TO_RESULT(fmt, fmt, message);
		fprintf(log_file, "%s", message.c_str());
		fflush(log_file);
	}
}

void registerManager(std::string probName, int num_processes, int argc, char* argv[]) {
	setName("manager for problem %s", probName.c_str());
	__testlib_ensuresPreconditions();
	testlibMode = _checker;
	random_t::version = 1; // Random generator version
	__testlib_set_binary(stdin);
	ouf.mode = _output;

	{//Keep alive on broken pipes
		//signal(SIGPIPE, SIG_IGN);
		struct sigaction sa;
		sa.sa_handler = SIG_IGN;
		sigaction(SIGPIPE, &sa, NULL);
	}

	int required_args = 1 + 2 * num_processes;
	if (argc < required_args || required_args+1 < argc) {
		string usage = format("'%s'", argv[0]);
		for (int i = 0; i < num_processes; i++)
			usage += format(" sol%d-to-mgr mgr-to-sol%d", i, i);
		usage += " [mgr_log] < input-file";
		quitf(_fail,
			"Manager for problem %s:\n"
			"Invalid number of arguments: %d\n"
			"Usage: %s",
			probName.c_str(), argc-1, usage.c_str());
	}

	inf.init(stdin, _input);
	closeOnHalt(stdout);
	closeOnHalt(stderr);

	mgr2sol.resize(num_processes);
	sol2mgr.resize(num_processes);
	for (int i = 0; i < num_processes; i++) {
		mgr2sol[i] = openFile(argv[1 + 2*i + 1], "a");
		sol2mgr[i] = openFile(argv[1 + 2*i + 0], "r");
	}

	if (argc > required_args) {
		log_file = openFile(argv[required_args], "w");
	} else {
		log_file = nullptr;
	}
}
/********************************* End testlib-related material *********************************/


// utils

#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)

template<class C> int sz(const C& c) { return std::size(c); }

#define log_var(var_name) log_printf("%s = %s\n", #var_name, toString(var_name).c_str());

template<class C>
void log_array(const C& c, string delim=" ", string ending="\n") {
	string d = "";
	for (const auto& x : c) {
		log_printf("%s%s", d.c_str(), toString(x).c_str());
		d = delim;
	}
	log_printf("%s", ending.c_str());
}


// grader/manager protocol

const int secret_g2m = 0x34508C80;
const int secret_m2g = 0x75EC8020;
const int code_mask  = 0x0000000F;

const int M2G_CODE__OK = 0;
const int M2G_CODE__DIE = 1;

const int G2M_CODE__OK_NEW_EXPERIMENT = 0;
const int G2M_CODE__OK_END_OF_EXPERIMENTS = 1;
const int G2M_CODE__INVALID_E_LENGTH = 2;
const int G2M_CODE__INVALID_G_LENGTH = 3;
const int G2M_CODE__PV_CALL_EXIT = 13;
const int G2M_CODE__PV_TAMPER_M2G = 14;
const int G2M_CODE__SILENT = 15;

int fifo_idx = 0;

enum class ActionMode {
	ok_new_experiment,
	ok_end_of_experiments,
} ok_action_mode;

void out_flush() {
	fflush(mgr2sol[fifo_idx]);
}

void write_int(int x) {
	if(1 > fprintf(mgr2sol[fifo_idx], "%d\n", x)) {
		nullifyFile(fifo_idx);
		log_printf("Could not write int to mgr2sol[%d]\n", fifo_idx);
	}
}

void write_secret(int m2g_code = M2G_CODE__OK) {
	write_int(secret_m2g | m2g_code);
}

#ifdef __GNUC__
__attribute__ ((format (printf, 2, 3)))
#endif
NORETURN void die(TResult result, const char* format, ...) {
	FMT_TO_RESULT(format, format, message);
	log_printf("Dying with message '%s'\n", message.c_str());
	rep(i, sz(mgr2sol))
		if(mgr2sol[i] != nullptr) {
			fifo_idx = i;
			log_printf("Sending secret with code DIE to mgr2sol[%d]\n", fifo_idx);
			write_secret(M2G_CODE__DIE);
			out_flush();
		}
	log_printf("Quitting with result code %d\n", int(result));
	quit(result, message);
}

NORETURN void die_invalid_argument(const string &msg) {
	RESULT_MESSAGE_WRONG += ": Invalid argument";
	die(_wa, "%s", msg.c_str());
}

NORETURN void die_too_many_calls(const string &msg) {
	RESULT_MESSAGE_WRONG += ": Too many calls";
	die(_wa, "%s", msg.c_str());
}

int read_int() {
	int x;
	if(1 != fscanf(sol2mgr[fifo_idx], "%d", &x)) {
		nullifyFile(fifo_idx);
		die(_fail, "Could not read int from sol2mgr[%d]", fifo_idx);
	}
	return x;
}

vector<int> read_int_vector(int len) {
	vector<int> v(len);
	rep(i, len)
		v[i] = read_int();
	return v;
}

void read_secret() {
	int secret = read_int();
	if((secret & ~code_mask) != secret_g2m)
		die(_pv, "Possible tampering with sol2mgr[%d]", fifo_idx);
	int g2m_code = secret & code_mask;
	switch (g2m_code) {
		case G2M_CODE__OK_NEW_EXPERIMENT:
			ok_action_mode = ActionMode::ok_new_experiment;
			return;
		case G2M_CODE__OK_END_OF_EXPERIMENTS:
			ok_action_mode = ActionMode::ok_end_of_experiments;
			return;
		case G2M_CODE__INVALID_E_LENGTH:
			die_invalid_argument("Invalid length of E");
		case G2M_CODE__INVALID_G_LENGTH:
			die(_wa, "Invalid length of G");
		case G2M_CODE__SILENT:
			die(_fail, "Unexpected g2m_code SILENT from sol2mgr[%d]", fifo_idx);
		case G2M_CODE__PV_TAMPER_M2G:
			die(_pv, "Possible tampering with mgr2sol[%d]", fifo_idx);
		case G2M_CODE__PV_CALL_EXIT:
			die(_pv, "Solution[%d] called exit()", fifo_idx);
		default:
			die(_fail, "Unknown g2m_code %d from sol2mgr[%d]", g2m_code, fifo_idx);
	}
}


// problem logic

const int CALLS_CNT_LIMIT = 2750;

int calls_cnt;

int N, M;
std::vector<std::vector<int>> adj;

int count_components(const std::vector<int>& S) {
	int components_cnt = 0;
	std::vector<bool> vis(N, false);
	for (int i = 0; i < N; i++) {
		if (vis[i])
			continue;
		components_cnt++;

		std::queue<int> q;
		vis[i] = true;
		q.push(i);
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (int nxt : adj[cur])
				if (!vis[nxt] && S[nxt] == S[cur]) {
					vis[nxt] = true;
					q.push(nxt);
				}
		}
	}
	return components_cnt;
}

int main(int argc, char *argv[]) {
	registerManager("sphinx", 1, argc, argv);

	// read input
	N = inf.readInt();
	M = inf.readInt();
	std::vector<int> C(N);
	rep(i, N)
		C[i] = inf.readInt();
	std::vector<int> X(M), Y(M);
	rep(j, M)
		X[j] = inf.readInt(), Y[j] = inf.readInt();

	adj.assign(N, vector<int>());
	rep(j, M) {
		adj[X[j]].push_back(Y[j]);
		adj[Y[j]].push_back(X[j]);
	}

	write_secret();
	write_int(N);
	write_int(M);
	rep(j, M)
		write_int(X[j]), write_int(Y[j]);
	out_flush();

	calls_cnt = 0;
	while (true) {
		read_secret();
		if (ok_action_mode != ActionMode::ok_new_experiment) break;

		std::vector<int> E = read_int_vector(N);

		calls_cnt++;
		if (calls_cnt > CALLS_CNT_LIMIT)
			die_too_many_calls("#experiments reached " + to_string(calls_cnt));

		rep(i, N)
			if (!(-1 <= E[i] && E[i] <= N))
				die_invalid_argument("Invalid value of E[" + to_string(i) + "]: " + to_string(E[i]));

		vector<int> S(N);
		rep(i, N)
			S[i] = (E[i] == -1 ? C[i] : E[i]);
		int P = count_components(S);

		write_secret();
		write_int(P);
		out_flush();
	}
	ensuref(ok_action_mode == ActionMode::ok_end_of_experiments, "Expected action code ok_end_of_experiments");
	log_printf("End of experiments.\n");

	std::vector<int> G = read_int_vector(N);

	// Scoring
	if (C == G)
		quitf(_ok, "#experiments: %d", calls_cnt);

	rep(i, N)
		if (!(0 <= G[i] && G[i] < N))
			quitf(_wa, "Invalid value of G[%d]: %d", i, G[i]);

	rep(j, M) {
		int x = X[j], y = Y[j];
		if (C[x] == C[y] && !(G[x] == G[y]))
			quitf(_wa, "Vertices %d and %d do have the same color, but they do not in returned answer", x, y);
		if (C[x] != C[y] && !(G[x] != G[y]))
			quitf(_wa, "Vertices %d and %d do not have the same color, but they do in returned answer", x, y);
	}
	quitp(50 / 100.0);
}

stub.cpp: #include "sphinx.h"
#include <cstdio>
#include <cstdlib>
#include <csignal>

using namespace std;


namespace {

/******************************** Begin testlib-related material ********************************/
#ifdef _MSC_VER
#   define NORETURN __declspec(noreturn)
#elif defined __GNUC__
#   define NORETURN __attribute__ ((noreturn))
#else
#   define NORETURN
#endif
/********************************* End testlib-related material *********************************/


// utils

#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)

template<class C> int sz(const C& c) { return std::size(c); }


// grader/manager protocol

const int secret_g2m = 0x34508C80;
const int secret_m2g = 0x75EC8020;
const int code_mask  = 0x0000000F;

const int M2G_CODE__OK = 0;

const int G2M_CODE__OK_NEW_EXPERIMENT = 0;
const int G2M_CODE__OK_END_OF_EXPERIMENTS = 1;
const int G2M_CODE__INVALID_E_LENGTH = 2;
const int G2M_CODE__INVALID_G_LENGTH = 3;
const int G2M_CODE__PV_CALL_EXIT = 13;
const int G2M_CODE__PV_TAMPER_M2G = 14;
const int G2M_CODE__SILENT = 15;


bool exit_allowed = false;

NORETURN void authorized_exit(int exit_code) {
  exit_allowed = true;
  exit(exit_code);
}


FILE* fin = stdin;
FILE* fout = stdout;

void out_flush() {
	fflush(fout);
}

void write_int(int x) {
	if(1 > fprintf(fout, "%d\n", x)) {
		fprintf(stderr, "Could not write int to fout\n");
		authorized_exit(3);
	}
}

void write_int_vector(const vector<int>& v) {
	rep(i, sz(v))
		write_int(v[i]);
}

void write_secret(int g2m_code) {
	write_int(secret_g2m | g2m_code);
}

NORETURN void die(int g2m_code) {
	if(g2m_code == G2M_CODE__OK_NEW_EXPERIMENT || g2m_code == G2M_CODE__OK_END_OF_EXPERIMENTS) {
		fprintf(stderr, "Shall not die with code OK\n");
		authorized_exit(5);
	}
	fprintf(stderr, "Dying with code %d\n", g2m_code);
	if(g2m_code != G2M_CODE__SILENT)
		write_secret(g2m_code);
	fclose(fin);
	fclose(fout);
	authorized_exit(0);
}

int read_int() {
	int x;
	if(1 != fscanf(fin, "%d", &x)) {
		fprintf(stderr, "Could not read int from fin\n");
		authorized_exit(3);
	}
	return x;
}

void read_secret() {
	int secret = read_int();
	if((secret & ~code_mask) != secret_m2g)
		die(G2M_CODE__PV_TAMPER_M2G);
	int m2g_code = secret & code_mask;
	if(m2g_code != M2G_CODE__OK)
		die(G2M_CODE__SILENT);
}

void check_exit_protocol() {
  if (!exit_allowed)
    die(G2M_CODE__PV_CALL_EXIT);
}


// problem logic

int N;

} // namespace


int perform_experiment(std::vector<int> E) {
	if (sz(E) != N) die(G2M_CODE__INVALID_E_LENGTH);
	write_secret(G2M_CODE__OK_NEW_EXPERIMENT);
	write_int_vector(E);
	out_flush();

	read_secret();
	int P = read_int();
	return P;
}

int main() {
	signal(SIGPIPE, SIG_IGN);
	atexit(check_exit_protocol);
	at_quick_exit(check_exit_protocol);

	read_secret();
	N = read_int();
	int M = read_int();
	std::vector<int> X(M), Y(M);
	rep(j, M)
		X[j] = read_int(), Y[j] = read_int();

	std::vector<int> G = find_colours(N, X, Y);

	if (sz(G) != N) die(G2M_CODE__INVALID_G_LENGTH);

	write_secret(G2M_CODE__OK_END_OF_EXPERIMENTS);
	write_int_vector(G);
	out_flush();

	exit_allowed = true;
	return 0;
}


Setup script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Setup Script (Sphinx Problem) ---"

# --- Fixed Files (Problem Specific) ---
STUB_CPP="stub.cpp"        # Stub for sphinx problem
MANAGER_CPP="manager.cpp"    # Manager for sphinx problem
HEADER="sphinx.h"           # Header for sphinx problem
TESTLIB_HEADER="testlib.h"   # Assumed present, needed by manager

# --- Argument Parsing ---
# Expect exactly one argument: solution_file
if [ "$#" -ne 1 ]; then
    echo "Usage: $0 <path/to/solution.cpp>" >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument

# --- File Checks (Compilation Prerequisites) ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools for compilation..."
check_file "$SOLUTION_CPP"
check_file "$STUB_CPP"
check_file "$MANAGER_CPP"
check_file "$HEADER"
# check_file "$TESTLIB_HEADER" # Check for testlib.h if needed
check_tool "g++"
echo "Checks passed."
echo "Setup for Solution: $SOLUTION_CPP"

# --- Dynamic Naming (Executables) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
# Executable for the user solution + stub
USER_EXE="./${SOLUTION_BASENAME}_sphinx_exe"
# Executable for the manager (fixed name for this problem type)
MANAGER_EXE="./sphinx_manager_exe"

# --- Compile User Solution (if it doesn't exist) ---
if [ ! -f "$USER_EXE" ]; then
    echo "Compiling solution ($SOLUTION_CPP + $STUB_CPP) into $USER_EXE ..."
    g++ -std=c++17 "$SOLUTION_CPP" "$STUB_CPP" -o "$USER_EXE" -I. -O2
    if [ $? -ne 0 ]; then
        echo "ERROR: Solution compilation failed." >&2
        exit 1
    fi
    echo "Solution compiled successfully."
else
    echo "Using existing solution executable: $USER_EXE"
fi

# --- Compile Manager (if it doesn't exist) ---
if [ ! -f "$MANAGER_EXE" ]; then
    echo "Compiling Manager ($MANAGER_CPP) into $MANAGER_EXE ..."
    g++ -std=c++17 "$MANAGER_CPP" -o "$MANAGER_EXE" -I. -O2
    if [ $? -ne 0 ]; then
        echo "ERROR: Manager compilation failed." >&2
        # Optional: remove user exe if manager fails?
        # rm -f "$USER_EXE"
        exit 1
    fi
    echo "Manager compiled successfully."
else
    echo "Using existing manager executable: $MANAGER_EXE"
fi

echo "Setup complete. Executables ready:"
echo "  Manager: $MANAGER_EXE"
echo "  Solution: $USER_EXE"

exit 0


Evaluation script:
#!/bin/bash
set -e # Exit immediately if a command fails

echo "--- Evaluation Script (Sphinx Problem) ---"

# --- Argument Parsing ---
# Expect exactly two arguments: solution_file and input_file
if [ "$#" -ne 2 ]; then
    echo "Usage: $0 <path/to/solution.cpp> <path/to/input.txt>" >&2
    echo "Note: Run setup.sh <path/to/solution.cpp> first to compile." >&2
    exit 1
fi
SOLUTION_CPP="$1" # Get solution file from first argument
INPUT_TXT="$2"    # Get input file from second argument

# --- File & Tool Checks ---
check_file() { if [ ! -f "$1" ]; then echo "ERROR: File not found: $1" >&2; exit 1; fi }
check_tool() { if ! command -v "$1" &> /dev/null; then echo "ERROR: Command not found: $1" >&2; exit 1; fi }

echo "Checking required files and tools for evaluation..."
check_file "$INPUT_TXT"
check_tool "mkfifo"
echo "Checks passed."
echo "Using Solution: $SOLUTION_CPP"
echo "Using Input:    $INPUT_TXT"

# --- Dynamic Naming (Consistent with setup.sh) ---
SOLUTION_BASENAME=$(basename "$SOLUTION_CPP" .cpp)
INPUT_BASENAME=$(basename "$INPUT_TXT" .in) # Assuming .in extension for inputs
# Executable names derived from solution basename (must match setup.sh)
USER_EXE="./${SOLUTION_BASENAME}_sphinx_exe"
# Fixed manager executable name (must match setup.sh)
MANAGER_EXE="./sphinx_manager_exe"
# Final result file from the manager
RESULTS_TXT="${INPUT_BASENAME}_${SOLUTION_BASENAME}.results.txt"

# Check if executables exist (created by setup.sh)
echo "Checking for compiled executables..."
check_file "$USER_EXE"
check_file "$MANAGER_EXE"
echo "Executables found."

# FIFO (Named Pipe) names for Inter-Process Communication (IPC)
# Using /tmp and PID ($$) for uniqueness to allow concurrent runs
FIFO_BASE="/tmp/sphinx_eval_${SOLUTION_BASENAME}_${INPUT_BASENAME}_$$"
MGR_TO_SOL="${FIFO_BASE}_m2s.fifo" # Manager -> Solution pipe
SOL_TO_MGR="${FIFO_BASE}_s2m.fifo" # Solution -> Manager pipe

# Initialize exit codes
SOLUTION_EXIT_CODE=-1
MANAGER_EXIT_CODE=-1

# --- Cleanup Function ---
# This function will be called on script exit (normal or error)
cleanup() {
    local script_exit_code=$?
    echo "Cleaning up evaluation run (Exit Code: $script_exit_code)..."
    # Kill background manager process if it's still running
    if [ -n "$MANAGER_PID" ] && ps -p $MANAGER_PID > /dev/null; then
       echo "Attempting to kill remaining Manager process (PID $MANAGER_PID)..."
       kill $MANAGER_PID 2>/dev/null || echo "Manager process (PID $MANAGER_PID) already finished or failed to kill."
    fi
    # Remove FIFOs
    echo "Removing FIFOs..."
    rm -f "$MGR_TO_SOL" "$SOL_TO_MGR"
    echo "Cleanup finished."
    # Exit with the original exit code that triggered the trap
    exit $script_exit_code
}
# Register the cleanup function to run on EXIT, INT, TERM signals
trap cleanup EXIT INT TERM

# --- Setup IPC ---
echo "Creating FIFOs for communication..."
mkfifo "$MGR_TO_SOL" "$SOL_TO_MGR"

# --- Run Processes ---
echo "Starting Manager process in background..."
# Manager expects arguments: sol->mgr pipe, mgr->sol pipe
"$MANAGER_EXE" "$SOL_TO_MGR" "$MGR_TO_SOL" < "$INPUT_TXT" > "$RESULTS_TXT" &
MANAGER_PID=$! # Store Manager's Process ID

echo "Starting Solution process in foreground..."
# The stub uses stdin/stdout, which are redirected to the pipes by the shell
# Use '|| true' temporarily to prevent set -e exit if solution fails
"$USER_EXE" < "$MGR_TO_SOL" > "$SOL_TO_MGR" || true
SOLUTION_EXIT_CODE=$? # Capture solution's exit code

# --- Wait and Check ---
# Wait for the manager process to finish and capture its exit code
echo "Waiting for Manager process (PID $MANAGER_PID) to finish..."
wait $MANAGER_PID || MANAGER_EXIT_CODE=$?
# If wait succeeded (manager exited 0), set MANAGER_EXIT_CODE to 0
if [ $? -eq 0 ]; then
    MANAGER_EXIT_CODE=0
fi

# --- Show Result ---
echo ""
echo "--- Evaluation Result ($RESULTS_TXT) ---"
# Check if results file exists and is readable before catting
if [ -r "$RESULTS_TXT" ]; then
    cat "$RESULTS_TXT"
else
    echo "ERROR: Result file '$RESULTS_TXT' not found or not readable." >&2
fi
echo "-----------------------------------------"

# --- Show Exit Codes ---
echo ""
echo "--- Process Exit Codes ---"
echo "Solution Exit Code: $SOLUTION_EXIT_CODE"
echo "Manager Exit Code:  $MANAGER_EXIT_CODE"
# Add warnings for non-zero exit codes
if [ $SOLUTION_EXIT_CODE -ne 0 ]; then
    echo "Warning: Solution process exited with non-zero status ($SOLUTION_EXIT_CODE)" >&2
fi
if [ $MANAGER_EXIT_CODE -ne 0 ]; then
    echo "Warning: Manager process exited with non-zero status ($MANAGER_EXIT_CODE)" >&2
fi
echo "--------------------------"

echo "--- Evaluation Complete ---"

# Exit the script with the manager's exit code
# The 'trap cleanup EXIT' will run before the script finally terminates
exit $MANAGER_EXIT_CODE