#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define int long long using namespace __gnu_pbds; using namespace std; const int mod = 1e6 + 3; const int inf = 1e9; const int maxx = 3e6 + 5; const int lg = 26; typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; int tmr = 0; set <pair <int, int> > s; vector <int> g1[maxx], g2[maxx], dis1(maxx), dis2(maxx), pre, suf; vector <bool> col1(maxx), col2(maxx); struct DSU { int n; vector <int> p; void init (int n) { p.assign (n + 1, -1); } int find (int a) { if (p[a] < 0) { return a; } return p[a] = find (p[a]); } bool unite (int a, int b) { a = find (a); b = find (b); if (a == b) { return 0; } if (p[a] < p[b]) { swap(a, b); } p[b] += p[a]; p[a] = b; return 1; } }; void dfs1(int u) { col1[u] = 1; for (auto to : g1[u]) { if (!col1[to]) { dfs1(to); } } pre.push_back(u); } void dfs2(int u) { col2[u] = 1; for (auto to : g2[u]) { if (!col2[to]) { dfs2(to); } } suf.push_back(u); } void solve () { int n, m, v; cin >> n >> m >> v; DSU dsu; dsu.init(m); vector <pair <int, int> > s; while (v--) { int a, b; char c; cin >> a >> c >> b; if (c == '=') { dsu.unite(a, b); } else { s.push_back({a, b}); } } for (auto [x, y] : s) { x = dsu.find(x); y = dsu.find(y); g1[x].push_back(y); g2[y].push_back(x); } for (int i = 1; i <= m; i++) { int j = dsu.find(i); if (!col1[j]) { dfs1(j); } } for (int i = 1; i <= m; i++) { int j = dsu.find(i); if (!col2[j]) { dfs2(j); } } reverse (pre.begin(), pre.end()); reverse (suf.begin(), suf.end()); for (auto x : pre) { for (auto to : g1[x]) { dis1[to] = max(dis1[to], dis1[x] + 1); } } for (auto x : suf) { for (auto to : g2[x]) { dis2[to] = max(dis2[to], dis2[x] + 1); } } for (int i = 1; i <= m; i++) { int j = dsu.find(i); if (dis1[j] + dis2[j] + 1 < n) { cout << '?' << endl; } else { cout << 'K' << dis1[j] + 1 << endl; } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } }