#include "bits/stdc++.h" using namespace std; #define int long long const int N = 3e5 + 5; int n, m, V; vector<int> adj[N], dag[N]; int q[N], nxt = 1; int dp[N]; int ans[N]; int par[N]; bool used[N], mark[N]; void dfs(int u) { used[u] = true; q[u] = nxt; for (int &v : adj[u]) { if (used[v]) continue; dfs(v); } } void clc(int u) { used[u] = true; for (int &v : dag[u]) { if (used[v]) continue; clc(v); } for (int &v : dag[u]) dp[u] = max(dp[u], dp[v] + 1); } void traverse(int u, int lev) { used[u] = true; ans[u] = lev; for (int &v : dag[u]) { if (used[v]) continue; par[u] = v; traverse(v, lev - 1); } if (dag[u].empty() && lev != 1) { ans[u] = 0; while (par[u]) { ans[u] = 0; u = par[u]; } } } void _() { cin >> n >> m >> V; vector<array<int, 2>> dir; for (int i = 0; i < V; ++i) { string s; cin >> s; int j = 0; while (isdigit(s[j])) ++j; string x = "", y = ""; char sym = s[j]; for (int k = 0; k < j; ++k) x += s[k]; ++j; while (j < size(s)) { y += s[j]; ++j; } int u = stoi(x), v = stoi(y); if (sym == '=') { adj[u].push_back(v); adj[v].push_back(u); } else dir.push_back({u, v}); } for (int i = 1; i <= m; ++i) { if (used[i]) continue; dfs(i), ++nxt; } for (auto &[u, v] : dir) { u = q[u], v = q[v]; dag[v].push_back(u); } for (int i = 1; i <= m; ++i) used[i] = false; for (int i = 1; i <= m; ++i) { if (used[i]) continue; clc(i); } vector<array<int, 2>> f; for (int i = 1; i <= m; ++i) { int x = dp[i]; f.push_back({i, x}); } sort (f.begin(), f.end(), [&](auto i, auto j) { return i[1] < j[1]; }); for (int i = 1; i <= m; ++i) used[i] = false; for (auto &[u, x] : f) { if (used[u] || x != n - 1) continue; traverse(u, x + 1); } for (int i = 1; i <= m; ++i) { if (!ans[q[i]]) cout << '?' << '\n'; else { cout << 'K' << ans[q[i]] << '\n'; } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) _(); } /* @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@}()))(([]}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]()<>>>^><>>><>><<<<(#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{})<<>**+++**+*^++*^^^^^^<<)#@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@%(^*>+++====~~~+=~~+==*=+*+*<^^[@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@#<**+^==+*~~----=+---=~-~~~~~==>**<}@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@{([*^==~~==-----:-=---:-:------~~>*++}@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@<^<=~~-~~-:::::::~:::::::::---=~=+=^^{@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%>))^=~---::::::.:.::.:..-::::::-~~^=+)){@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@##))^~~~-~+::::.......:..:.-:::-:=~+<+>]{%@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%(()*=*~*=^:~:-.::.::.:....~::::-=~+)<^(%@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@}}()>+***<^-^-~:~::*-.~::::=----=*=^>))]{@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@%@]])<<^)*])~<~=:++-)+-^---:*~--~+><>)))[%@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%[{()]<])%<=<+>-><=)>~)=~=~^==~=*<<)<(){@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%@@]([){[]})(*)+)]*]]=]]=++^*+~^)(<)[(]#@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@}{(<<<>)]}>()]}]{[<))^*)>^**<})([]<}%@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^^)]<*()[]]<>>)<^]<<<>(]>(}[}@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^([>>^^^^^>^^^^>>>)()<<>]]]@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@[>^>[[)>^^^^^^^^^^^^^><<]<>><]@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@#>>^]]>^^^^^^^^^^^^^^>^^(>{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@(>>>({[}[^^^^^^^^^^^^^^>[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@(>><>>^^^^^^^^^^^^^^^>){%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@%<>]><>^^^^^^^^^^^^><]}}}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{<><])<><<^^^^^>)[}}{[[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{[>>^^^^^^^^>)[{}}}}}[}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%}[>>^^^^>){}}}}}}}}}}[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}#{}[}}}}}}}}}}}}}()%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@%@@@@@@@@@@@@@@}}}}{}}}}}}}}}}}}}]>>(%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{}}}{}}}}}}}}}}}})>>>]}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@%{{}}}}}}}}}}}}]<]<>>>>>[}%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}{[[}}}[)>>))>>>>>><[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}}}))(>>>>>[>>>>>>>><{@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}})>>[{<>>>^^()<<>>>>>><}@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{)<<>><[}>>>>>[<](>>><<}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]<<(]>><}])[{#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ */