Language: C++

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair <int, int> pii;

const int MAXN = 5e4 + 5;
const int MAXM = 1e5 + 5;
const int SQRT = 450;

int N, M, T;
bitset <MAXN> state[MAXN];
int x[MAXM], y[MAXM];
bitset <MAXM> changes[SQRT][SQRT];
bool adj[SQRT][SQRT];
char ans[MAXM];

void load() {
	scanf("%d%d%d", &N, &M, &T);
	for (int i = 0; i < M; i++) {
		scanf("%d%d", x + i, y + i);
		x[i]--;
		y[i]--;
	}
}

void reconstruct(int final) {
	vector <bool> curr(N, false);
	curr[final] = true;
	for (int i = M - 1; i >= 0; i--)
		if (!curr[x[i]]) {
			ans[i] = 'v';
			if (curr[y[i]])
				curr[x[i]] = true;
		}
		else {
			ans[i] = '^';
			if (curr[x[i]])
				curr[y[i]] = true;
		}
	puts(ans);
}

void uniforming() {
	for (int i = 0; i < N; i++)
		state[i].set(i);
	
	for (int i = M - 1; i >= 0; i--)
		state[x[i]] = state[y[i]] = state[x[i]] | state[y[i]];
	
	bitset <MAXN> all;
	all.set();
	for (int i = 0; i < N; i++)
		all &= state[i];
	
	for (int i = 0; i < N; i++)
		if (all.test(i)) {
			reconstruct(i);
			return;
		}
	
	puts("-1");
}

void finish(int u, int v) {
	for (int i = 0; i < M; i++) {
		bool flag = false;
		for (int j = 0; j < 2; j++) {
			if (changes[u][v].test(i) && (u == x[i] || u == y[i])) {
				ans[i] = u == x[i] ? 'v' : '^';
				u = x[i] ^ y[i] ^ u;
				flag = true;
				break;
			}
			swap(u, v);
		}
		if (flag)
			continue;
		if (x[i] == u || x[i] == v) 
			ans[i] = '^';
		else
			ans[i] = 'v';
	}
	puts(ans);
}

void update(int u, int v, vector <pii> &t) {
	for (int i = 0; i < N; i++)
		if (adj[u][i]) 
			t.push_back({v, i});
}

void output_adj() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf("%d ", adj[i][j]);
		puts("");
	}
	puts("");
}

void output_changes() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			printf("%d %d: ", i, j);
			for (int k = 0; k < M; k++)
				if (changes[i][j].test(k))
					printf("%d ", k);
			puts("");
		}
}

void non_uniforming() {
	map <pii, int> bio;
	for (int i = 0; i < M; i++)
		bio[{x[i], y[i]}] = true;
	
	int sofar = 0;
	for (int i = 0; i < N && sofar <= M; i++)
		for (int j = i + 1; j < N && sofar <= M; j++) {
			if (!bio[{i, j}]) {
				finish(i, j);
				return;
			}
			sofar++;
		}
	
	assert(N < SQRT);	
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			adj[i][j] = i != j;
	
	for (int i = M - 1; i >= 0; i--) {
		adj[x[i]][y[i]] = adj[y[i]][x[i]] = false;
		vector <pii> todo;
		update(x[i], y[i], todo);
		update(y[i], x[i], todo);
		for (auto it : todo) {
			adj[it.first][it.second] = adj[it.second][it.first] = true;
			changes[it.first][it.second].set(i);
		}
	}
		
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++)
			if (adj[i][j]) {
				finish(i, j);
				return;
			}
		
	puts("-1");
}

void check() {
	if (ans[0] != 'v' && ans[0] != '^')
		return;
	set <int> possible;
	for (int i = 0; i < N; i++) {
		int curr = i;
		for (int j = 0; j < M; j++) {
			if (curr == x[j] && ans[j] == 'v')
				curr = y[j];
			if (curr == y[j] && ans[j] == '^')
				curr = x[j];
		}
		possible.insert(curr);
	}
	bool ok = (possible.size() == 1) ^ (T == 2);
	if (ok)
		puts("ok");
	else {
		puts("wrong answer");
		printf("%d %d %d\n", N, M, T);
		for (int i = 0; i < M; i++)
			printf("%d %d\n", x[i] + 1, y[i] + 1);
	}
}

void gen() {
	N = 3;
	M = 3;
	T = 2;
	for (int i = 0; i < M; i++) {
		y[i] = uniform_int_distribution <int>(1, N - 1)(rng);
		x[i] = uniform_int_distribution <int>(0, y[i] - 1)(rng);
	}
}

int main() {
	load();
	//gen();
	if (T == 1)
		uniforming();
	else
		non_uniforming();
	//check();
	return 0;
}

Compiler output:
/tmp/cc5BtVDK.o: in function `reconstruct(int)':
a.cc:(.text+0x1f8): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
a.cc:(.text+0x29a): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
a.cc:(.text+0x33c): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
/tmp/cc5BtVDK.o: in function `finish(int, int)':
a.cc:(.text+0x6ba): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
a.cc:(.text+0x76a): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
a.cc:(.text+0x77c): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
a.cc:(.text+0x79d): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc5BtVDK.o
/tmp/cc5BtVDK.o: in function `update(int, int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&)':
a.cc:(.text+0x7df): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/cc5BtVDK.o
/tmp/cc5BtVDK.o: in function `output_adj()':
a.cc:(.text+0x863): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/cc5BtVDK.o
/tmp/cc5BtVDK.o: in function `non_uniforming()':
a.cc:(.text+0xb74): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/cc5BtVDK.o
a.cc:(.text+0xbee): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status