// We were born for this
#include <array>
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define line() "author : AyazN";
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int sz = 300500, inf = 1000000000, LOG = 30;
const ll mod = 1000000007, INF = 1000000000000000000;
int ans[sz], out[sz], in[sz];
int id[sz], dep[sz];
vi g[sz], g2[sz], g3[sz];
bool used[sz], ok;
struct DSU {
vi p, sz;
int n, compo;
void init(int _n) {
n = _n;
compo = n;
p.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) p[i] = i;
}
int getpar(int x) {
if (p[x] != x) p[x] = getpar(p[x]);
return p[x];
}
void connect(int x, int y) {
int a = getpar(x);
int b = getpar(y);
if (a == b) return;
if (out[a] == 0 && out[b]) std::swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
bool same(int x, int y) {
return getpar(x) == getpar(y);
}
};
int n, mx;
void dfs(int v) {
used[v] = 1;
for (auto u : g2[v]) {
u = id[u];
if (used[u]) continue;
dfs(u);
}
}
int m;
pii bfs(int s) {
vi dep(m + 1, inf);
queue<int> q;
s = id[s];
q.push(s);
dep[s] = 0;
int mxNode = q.front();
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : g[v]) {
u = id[u];
if (dep[u] != inf) continue;
dep[u] = dep[v] + 1;
q.push(u);
if (dep[mxNode] < dep[u]) {
mxNode = u;
}
}
}
return {mxNode, dep[mxNode]};
}
void dfsAns(int u) {
if (ans[u] == -1) return;
for (auto v : g[u]) {
v = id[v];
if (ans[v] != -1) continue;
ans[v] = ans[u] + 1;
dfsAns(v);
}
}
int dfsAns2(int u) {
if (ans[u] != -1) return ans[u];
for (auto v : g[u]) {
v = id[v];
ans[u] = dfsAns2(v) - 1;
}
return ans[u];
}
pii bfs2(int s) {
vi dep(m + 1, inf);
queue<int> q;
s = id[s];
q.push(s);
dep[s] = 0;
int mxNode = q.front();
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : g3[v]) {
u = id[u];
if (dep[u] != inf) continue;
dep[u] = dep[v] + 1;
q.push(u);
if (dep[mxNode] < dep[u]) {
mxNode = u;
}
}
}
return {mxNode, dep[mxNode]};
}
void precompute() {}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
// freopen("err.log", "w", stderr);
#endif
precompute();
int v;
cin >> n >> m >> v;
for (int i = 1; i <= m; i++) {
ans[i] = -1;
}
vpii edges;
vector<array<int, 3>> op;
DSU d; d.init(m);
for (int i = 1; i <= v; i++) {
int a, b;
char c;
cin >> a >> c >> b;
op.push_back({a, b, int(c)});
if (c == '=') {
d.connect(a, b);
continue;
}
edges.emplace_back(a, b);
}
for (int i = 1; i <= m; i++) {
id[i] = d.getpar(i);
}
for (auto [u, v] : edges) {
in[id[u]]++;
g[id[u]].emplace_back(id[v]);
g2[id[v]].emplace_back(id[u]);
g2[id[u]].emplace_back(id[v]);
g3[id[v]].emplace_back(id[u]);
}
for (int i = 1; i <= m; i++) {
int u = id[i];
if (used[u]) continue;
dfs(u);
auto [x, X] = bfs(u);
auto [_, y] = bfs2(x);
debug(y);
if (y != n - 1) continue;
queue<int> q;
q.push(_);
ans[_] = 1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
to = id[to];
if (ans[to] != -1) continue;
q.push(to);
ans[to] = ans[v] + 1;
}
}
for (int i = 1; i <= m; i++) cout << ans[i] << " ";
cout << endl;
}
for (int i = 1; i <= m; i++) {
int u = id[i];
dfsAns(u);
}
for (int i = 1; i <= m; i++) {
int u = id[i];
dfsAns2(u);
}
for (int i = 1; i <= m; i++) {
int u = id[i];
if (ans[u] == -1) {
cout << "?\n";
} else {
cout << "K" << ans[u] << '\n';
}
}
}
