#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> using namespace std; // using namespace __gnu_pbds; // template <typename T> // using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define pb push_back #define eb emplace_back #define pf push_front #define ppb pop_back #define ppf pop_front #define ins insert #define ff first #define ss second // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr int inf = 1e15, mod = 998244353, maxn = 1000005; int n, m, V; vector<vector<int>> g1, g; vector<int> compress, res; vector<bool> vis; vector<vector<int>> rr; void dfs1(int u, int id){ vis[u]=true; compress[u]=id; rr[id].pb(u); for (int v: g1[u]){ if (!vis[v]){ dfs1(v, id); } } } vector<int> topo; void dfs(int u){ vis[u] = true; for (int v: g[u]){ if (!vis[v]){ dfs(v); } } topo.pb(u); } void solve(){ cin >> n >> m >> V; vector<pair<int,int>> edges; g1.assign(m+1, vector<int>()); compress.assign(m+1, -1); rr.assign(m+1, vector<int>()); vis.assign(m+1, true); for (int i = 0; i < V; i++){ int u=0, v=0; char cc='*'; string l; cin >> l; for (char c: l){ if ('0'<=c&&c<='9'){ if (cc=='*'){ u*=10; u+=(c-'0'); } else{ v*=10; v+=(c-'0'); } } else{ cc=c; } } if (cc=='='){ g1[u].pb(v); g1[v].pb(u); vis[u]=vis[v]=false; } else{ edges.eb(u, v); } } for (int u = 1; u <= m; u++){ if (!vis[u]){ dfs1(u, u); } } g.assign(m+1, vector<int>()); vector<int> in(m+1, 0); vector<vector<int>> gr(m+1); for (auto [u, v]: edges){ if (0<compress[u]&&0<compress[v]){ g[compress[u]].pb(compress[v]); gr[compress[v]].pb(compress[u]); in[compress[v]]++; } else if (0<compress[u]){ g[compress[u]].pb(v); gr[v].pb(compress[u]); in[v]++; } else if (0<compress[v]){ g[u].pb(compress[v]); gr[compress[v]].pb(u); in[compress[v]]++; } else{ g[u].pb(v); gr[v].pb(u); in[v]++; } } res.assign(m+1, -1); vis.assign(m+1, false); for (int u = 1; u <= m; u++){ if (!in[u]){ dfs(u); } } reverse(topo.begin(), topo.end()); vector<int> mxIn(m+1), mxOut(m+1); for (int u: topo){ for (int v: gr[u]){ mxIn[u] = max(mxIn[u], mxIn[v]+1); } } for (int i = topo.size()-2; 0 <= i; --i){ int u = topo[i]; for (int v: g[u]){ mxOut[u] = max(mxOut[u], mxOut[v]+1); } } for (int u = 1; u <= m; u++){ if (mxIn[u]+mxOut[u]==n-1){ res[u] = mxIn[u]+1; } } for (int i = 1; i <= m; i++){ for (int v: rr[i]){ res[v] = res[i]; } } for (int i = 1; i <= m; i++){ if (res[i]<0){ cout << "?\n"; } else{ cout << "K" << res[i] << '\n'; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 0; i < t; i++) { solve(); } return 0; }