有 \(n\) 条线 \(m\) 个平衡器，从左往右第 \(i\) 个平衡器连接了 \(x_i,y_i\) 条电线（\(1\le x_i<y_i\le n\)），每个平衡器都有一个状态：向上或向下。考虑一个令牌，从最左边的某一条导线开始，如果在第 \(i\) 个位置，如果他在 \(x_i\) 导线上且平衡器状态向下，那么就到 \(y_i\)，同理如果在 \(y_i\) 且状态向上，则到 \(x_i\)。记 \(k_i\) 表示令牌从导线 \(i\) 开始到无穷远处是他在哪条导线上。
让你构造两种解，每种解用一个字符串表示，表示每个平衡器的状态。第一组解要求所有的 \(k_i\) 相等，第二组接要求至少有两个 \(k_i\) 不相等。无解输出 \(-1\)。
数据范围 \(2\le n\le 5\times 10^4,\,1\le m\le 10^5\)。
一道有趣的构造题。
首先我们考虑构造第一组解。我们考虑从后往前做，枚举 \(t\) 判断是否有一组解使得最终所有 \(k_i=t\)。令 \(f_{i,j}\) 表示仅有最后 \(i\) 个平衡器时，第 \(j\) 条线上的令牌是否到了 \(t\)。考虑在最前面加一个平衡器。发现其实就是 \(f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,x_j}\vee f_{i,y_{n-i}}\)。因为只要有一条线上可以到达 \(t\)，我们可以将两条线上的令牌都导到这条线上。
考虑上面的做法将第一维滚掉之后是 \(\mathcal{O}(m)\) 的，于是我们得到了一个 \(\mathcal{O}(nm)\) 的算法。考虑优化，我们令 \(g_{i,j,t}\) 表示最后 \(i\) 个，第 \(j\) 条线是否能到达 \(t\)。我们考虑转移就是 \(g_{i+1,x_{n-i},t}=g_{i+1,y_{n-i},t}=g_{i,x_{n-i},t}\vee g_{i,y_{n-i},t}\)。不难发现这个东西可以用 bitset 进行优化。常数 \(\frac{1}{64}\)，可以过。
然后考虑构造，这就简单了，直接沿着一个有解的 \(t\)，继续做一遍上面的 dp 即可。
然后考虑第二问，首先我们发现之后当 \(n=2\) 的时候才会发生无解。其余时刻都不会，至于为什么，我们考虑一下的构造方法。
仍然考虑倒着做，\(f_{i,j}\) 表示加入最后的 \(i\) 个平衡器，第 \(j\) 根线上的令牌现在在哪儿。
我们考虑加入一个令牌，那只会有两种状态：\(f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,x_{n-i}}\) 或是 \(f_{i+1,x_{n-i}}=f_{i+1,y_{n-i}}=f_{i,y_{n-i}}\)。而最终的目的是让至少有两个 \(f\) 值是不相等的。那么我们考虑 \(g_{i,j}\) 表示 \(f_{i,k}=j\) 的数量。这样我们只要比较两个 \(f\) 的 \(g\)，看看那个多，让多的给少的一个。考虑到 \(n>2\)，每次将一个 \(g\) 加 \(1\)，一个 \(g\) 减 \(1\)。不难发现一定有两个 \(g\) 是大于 \(0\) 的。于是一定有一种方案合法。
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x * 10) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
#define lowbit(x) (x & -x)
namespace dfcmd {
const int maxn = 50005;
const int maxm = 100005;
int n, m, T;
struct Balancer {
int x, y;
} bal[maxm];
char ans[maxm];
int ff[maxn];
namespace solve1 {
bitset<maxn> f[maxn];
inline void solve() {
for (int i = 1; i <= n; ++i) {
f[i][i] = 1;
}
for (int i = m; i; --i) {
f[bal[i].x] = f[bal[i].y] = f[bal[i].x] | f[bal[i].y];
}
for (int i = 2; i <= n; ++i) {
f[1] &= f[i];
}
int now = 0;
for (int i = 1; i <= n; ++i) {
if (f[1][i]) {
now = i;
break;
}
}
if (!now) {
puts("-1");
return;
}
ff[now] = 1;
for (int i = m; i; --i) {
if (ff[bal[i].x]) {
ans[i] = '^';
} else {
ans[i] = 'v';
}
ff[bal[i].x] = ff[bal[i].y] = ff[bal[i].x] | ff[bal[i].y];
}
puts(ans + 1);
}
}
namespace solve2 {
int g[maxn];
inline void solve() {
if (n == 2) {
puts("-1");
return;
}
for (int i = 1; i <= n; ++i) {
ff[i] = i;
g[i] = 1;
}
for (int i = m; i; --i) {
if (g[ff[bal[i].x]] < g[ff[bal[i].y]]) {
g[ff[bal[i].x]]++, g[ff[bal[i].y]]--;
ff[bal[i].y] = ff[bal[i].x];
ans[i] = '^';
} else {
g[ff[bal[i].x]]--, g[ff[bal[i].y]]++;
ff[bal[i].x] = ff[bal[i].y];
ans[i] = 'v';
}
}
puts(ans + 1);
}
}
int Main() {
read(n), read(m), read(T);
for (int i = 1; i <= m; ++i) {
read(bal[i].x), read(bal[i].y);
}
if (T == 1) {
solve1::solve();
} else {
solve2::solve();
}
return 0;
}
}
int main() {
return dfcmd::Main();
}