神仙构造题。写一下 pb 讲的做法。

考虑极差不超过 $2$ 这个限制。可以把每条边 $u,v$ ，令 $u<v$ ，则变成 $u,v+n$ 的一条边，也就是拆成一个二分图。

考虑在这个图上染色，然后再把 $u,u+n$ 合并起来。如果在这个得到的二分图上可以染色使得每个点极差不超过 $1$ ，那么合并后一定可以让每个点极差不超过 $2$ 。

下面将说明这样的合法的染色方案一定存在。假设一个点 $u$ 的度数是 $ak+b$ ，那么我们可以把一个点拆成 $a+1$ 个点，然后前 $a$ 个点分别得到原二分图上 $u$ 的任意 $k$ 个出边，最后一个得到 $b$ 个出边。然后我们就需要染色后使得每个点的的所有出边颜色不同。

考虑一条边一条边进行染色。假设当前边的两端是 $u,v$ 。现在我们任意找到 $u,v$ 的一对还没有用过的颜色 $c_u,c_v$ 。如果有 $c_u = c_v$ ，显然可以直接给这条边染色。否则，我们把这条边置为 $c_u$ ，然后去寻找一条 $v$ 的出边使得颜色也是 $c_u$ ，假设这条边连向 $w$ ，把这条边置为 $c_v$ ，然后再去找 $w$ 的一条出边使得这条出边是 $c_u$ ，再置为 $c_v$ $\dots$ 就这么一直操作下去。注意，我们寻找的颜色一定是 $c_u,c_v$ 之一。大致过程长成这样：

image.png

这么一直操作下去，最后一定不会出现环。如果出现了，显然必然是一个偶环。画图一下会发现

image.png

这种情况必然对应着图中的虚线边，这就意味着 $c_u$ 并不是一个合法的颜色，或者意味着之前的染色方案并不合法。因此，一定不会找到环。所以按照这样的方式一直染色即可找到一组合法的方案。

最坏情况下，对于每条边可能都需要遍历整张图，复杂度是 $O(mn^2)$ 大概，可以通过这个题。

cpp

typedef long long ll;
int n , m , k;
int A[MAXN];

pii ed[MAXN];
map<pii,int> M;
int deg[MAXN] , sz[MAXN] , st[MAXN] , cu[MAXN];
vector<pii> G[MAXN];

void doit( int pr , int u , int fd , int go ) {
	for( auto& t : G[u] ) if( t.fi == fd ) {
		t.fi = go;
		doit( u , t.se , go , fd );
	}
	for( auto& t : G[u] ) if( t.se == pr ) t.fi = fd;
}

int as[MAXN];

void solve() {
	cin >> n >> m >> k;
	rep( i , 1 , n ) scanf("%*d");
	rep( i , 1 , m ) {
		int u , v;
		scanf("%d%d",&u,&v);
		if( u > v ) swap( u , v );
		ed[i] = mp( u , v + n );
		++ deg[u] , ++ deg[v + n];
	}
	n = n << 1;
	st[0] = 1;
	rep( i , 1 , n ) sz[i] = ( deg[i] + k - 1 ) / k , st[i] = st[i - 1] + sz[i - 1];
	rep( i , 1 , m ) {
		int u = ed[i].fi , v = ed[i].se;
		G[st[u]].eb( mp( 0x3f3f3f3f , st[v] ) );
		G[st[v]].eb( mp( 0x3f3f3f3f , st[u] ) );
		ed[i] = mp( st[u] , st[v] );
		M[ed[i]] = i;
		++ cu[u] , ++ cu[v];
		if( cu[u] == k ) ++ st[u] , cu[u] = 0;
		if( cu[v] == k ) ++ st[v] , cu[v] = 0;
	}
	rep( i , 1 , m ) {
		int u = ed[i].fi , v = ed[i].se , fuck = 0 , kcuf = 0;
//		cout << u << ' ' << v << endl;
		sort( all( G[u] ) ) , sort( all( G[v] ) );
		for( int i = 0 ; i < G[u].size() ; ++ i ) if( i + 1 != G[u][i].fi ) {
			fuck = i + 1; break;
		}
		for( int i = 0 ; i < G[v].size() ; ++ i ) if( i + 1 != G[v][i].fi ) {
			kcuf = i + 1; break;
		}
		for( auto& t : G[u] ) if( t.se == v ) t.fi = fuck;
		doit( u , v , fuck , kcuf );
	}
	rep( i , 1 , st[n] ) for( auto t : G[i] ) if( i < t.se ) {
		as[M[mp( i , t.se )]] = t.fi;
	}
	rep( i , 1 , m ) printf("%d\n",as[i]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}