首先把染色变成差分，然后抽象成两个点(l, r+1)，连一条有向边，染色就是方向，要求每个点的前缀和(S in[-1, 1])。
把差为(1)的变成(0)，就把差为(1)的部分覆盖一个区间（连一条无向边），这样就可以全部转化为差为(0)的情况。
发现这是一个欧拉回路（图不保证连通可能有多条）：从(S)开始，每走一条正向边相当于给这段区间(+1)，反向边相当于(-1)，因为欧拉路径最终会回到(S)，因此所有点覆盖的和为(0)。
所以网络流构造欧拉路即可，方法网上有。
Code
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
typedef long long ll;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
char getc () {return gc();}
inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
template <class I> inline void gi (I &x) {for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;}
template <class I> inline void print (I x) {if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;while (x) qu[++ qr] = x % 10 + '0', x /= 10;while (qr) putc (qu[qr --]);}
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi; using io :: putc; using io :: print; using io :: getc;
template<class T> void upmax(T &x, T y){x = x>y ? x : y;}
template<class T> void upmin(T &x, T y){x = x<y ? x : y;}
const int Node = 60010, Edge = 240020, N = 30005;
struct NetworkFlows{
int hd[Node], to[Edge], nt[Edge], cur[Node], ec = 0;
int f[Edge];
int S, T, h[Node];
int cycle = 0;
void clear(){ec = 0; memset(hd, -1, sizeof(hd));}
NetworkFlows(){clear();}
int link(int x, int y, int flow){
to[ec] = y; nt[ec] = hd[x]; hd[x] = ec; f[ec] = flow; ++ec;
to[ec] = x; nt[ec] = hd[y]; hd[y] = ec; f[ec] = 0; ++ec;
return ec - 2;
}
bool bfs(){
memset(h, -1, sizeof(h));
memset(cur, -1, sizeof(cur));
static int q[Node];
int l = 0, r = 1;
q[l] = S; h[S] = 0;
while(l < r){
int x = q[l++];
for(int i=hd[x]; i!=-1; i=nt[i])
if(f[i] && h[to[i]] == -1) h[to[i]] = h[x] + 1, q[r++] = to[i];
}
return h[T] != -1;
}
int dfs(int x, int flow){
if(!flow || x == T) return flow;
int res = 0;
if(cur[x] == -1) cur[x] = hd[x];
for(int i=cur[x]; i!=-1; i=nt[i], cur[x]=i){
if(h[to[i]] != h[x] + 1) continue;
int aug = min(flow, f[i]);
if((aug = min(aug, dfs(to[i], aug)))){
f[i] -= aug; f[i ^ 1] += aug;
flow -= aug; res += aug;
}
if(!flow) return res;
}
if(res == 0) h[x] = -1;
return res;
}
int maxflow(){
int res = 0;
while(bfs()) res += dfs(S, 0x3f3f3f3f), ++cycle;
return res;
}
}G;
int p[Node], pc = 0, l[N], r[N], w[N];
int ind[Node], outd[Node];
int odd[Node], oc = 0;
int eid[N];
int main(){
int n, _;
gi(n); gi(_);
for(int i=1; i<=n; i++){
gi(l[i]); gi(r[i]); gi(w[i]);
++r[i];
p[++pc] = l[i]; p[++pc] = r[i];
}
sort(p+1, p+1+pc);
pc = unique(p+1, p+1+pc) - p - 1;
G.S = pc + 1; G.T = pc + 2;
for(int i=1; i<=n; i++){
l[i] = lower_bound(p+1, p+1+pc, l[i]) - p;
r[i] = lower_bound(p+1, p+1+pc, r[i]) - p;
if(w[i] == 1) ++outd[l[i]], ++ind[r[i]];
else ++ind[l[i]], ++outd[r[i]];
if(w[i] == -1) eid[i] = G.link(l[i], r[i], 1);
odd[++oc] = l[i]; odd[++oc] = r[i];
}
sort(odd+1, odd+1+oc);
for(int i=1; i<oc; i+=2){
if(odd[i] == odd[i+1]) continue;
++ind[odd[i]]; ++outd[odd[i + 1]];
G.link(odd[i], odd[i+1], 1);
}
int sum = 0, isum = 0;
for(int i=1; i<=pc; i++){
int adj = (ind[i] - outd[i]) / 2;
if(adj > 0) G.link(G.S, i, adj), sum += adj;
else if(adj < 0) G.link(i, G.T, -adj), isum -= adj;
}
int flow = G.maxflow();
if(flow != sum){
puts("-1");
return 0;
}
else
for(int i=1; i<=n; i++)
if(w[i] == -1) printf("%d ", G.f[eid[i]] ^ 1);
else printf("%d ", w[i]);
putchar('
');
return 0;
}