#include <bits/stdc++.h>
//#define LOCAL
#ifndef LOCAL
#include "Anthony.h"
#endif
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
const int N = (int)2e4 + 9;
const int mod = (int)1e9 + 7;
pair<int, int> e[N];
namespace {
int par[N];
int n, m;
vector<ii> g[N];
};
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
n = N, m = M;
for(int i = 0; i < m; ++i) e[i] = _mp(U[i], V[i]);
vec<int> mark(m);
if (B == 0 and A >= 3) {
for(int i = 0; i < m; ++i) {
g[e[i].fi].emplace_back(e[i].se, i);
g[e[i].se].emplace_back(e[i].fi, i);
}
queue<int> q;
vec<int> h(n, -1);
q.push(0);
h[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for(ii v : g[u]) {
if (h[v.fi] == -1) {
h[v.fi] = h[u] + 1;
par[v.fi] = u;
q.push(v.fi);
}
}
}
for(int i = 0; i < m; ++i) {
if (h[ e[i].fi ] > h[ e[i].se ]) swap(e[i].fi, e[i].se);
if (h[ e[i].fi ] == h[ e[i].se ]) {
mark[i] = (h[e[i].fi] % 3);
continue;
}
mark[i] = (h[ e[i].se ] - 1) % 3;
}
return mark;
}
return mark;
}
#ifdef LOCAL
int main() {
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int n, m, a, b, s;
cin >> n >> m >> a >> b >> s;
vector<int> U(m), V(m);
for(int i = 0; i < m; ++i) {
cin >> U[i] >> V[i];
}
vector<int> f = Mark(n, m, a, b, U, V);
for(int i = 0; i < m; ++i)
cout << f[i] << ' ';
}
#endif
#include <bits/stdc++.h>
//#define LOCAL
#ifndef LOCAL
#include "Catherine.h"
#endif
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
namespace {
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
int A, B;
int variable_example = 0;
}; // namespace
void Init(int A, int B) {
::A = A;
::B = B;
}
int Move(vector<int> y) {
int cnt = 0;
for(int j = 0; j < A; ++j) {
cnt += y[j] > 0;
}
if (cnt == 1) {
for(int j = 0; j < A; ++j) if (y[j] > 0)
return j;
}
if (y[0] and y[1]) return 0;
if (y[1] and y[2]) return 1;
if (y[0] and y[2]) return 2;
// no more case
return -1;
}
#ifdef LOCAL
int main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
}
#endif
/* Let the river flows naturally */
