#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], rdag[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 (u == 1) cout << ans[2] << ' ' << ans[3] << '\n'; // 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); rdag[u].push_back(v); } 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) ans[i] = 1e9; function<int(int)> solve = [&](int u) -> int { if (dp[u] == n - 1) return ans[u] = n; else if (ans[u] != 1e9) return ans[u]; int res = 1e9; for (int &v : rdag[u]) { res = min(res, solve(v) - 1); } return ans[u] = res; }; for (int i = 1; i <= m; ++i) solve(q[i]); // for (int i = 1; i <= m; ++i) // { // int u = q[i]; // for (int &v : rdag[u]) // { // ans[u] = min(ans[u], ans[v] - 1); // } // } // for (int i = 1; i <= m; ++i) // { // int u = q[i]; // if (dag[u].empty() && ans[u] != 1) // { // ans[u] = 0; // while (par[u]) // { // ans[u] = 0; // u = par[u]; // } // } // } for (int i = 1; i <= m; ++i) { if (ans[q[i]] == 1e9) 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--) _(); } /* @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@}()))(([]}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]()<>>>^><>>><>><<<<(#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{})<<>**+++**+*^++*^^^^^^<<)#@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@%(^*>+++====~~~+=~~+==*=+*+*<^^[@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@#<**+^==+*~~----=+---=~-~~~~~==>**<}@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@{([*^==~~==-----:-=---:-:------~~>*++}@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@<^<=~~-~~-:::::::~:::::::::---=~=+=^^{@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%>))^=~---::::::.:.::.:..-::::::-~~^=+)){@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@##))^~~~-~+::::.......:..:.-:::-:=~+<+>]{%@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%(()*=*~*=^:~:-.::.::.:....~::::-=~+)<^(%@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@}}()>+***<^-^-~:~::*-.~::::=----=*=^>))]{@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@%@]])<<^)*])~<~=:++-)+-^---:*~--~+><>)))[%@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%[{()]<])%<=<+>-><=)>~)=~=~^==~=*<<)<(){@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@%@@]([){[]})(*)+)]*]]=]]=++^*+~^)(<)[(]#@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@}{(<<<>)]}>()]}]{[<))^*)>^**<})([]<}%@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^^)]<*()[]]<>>)<^]<<<>(]>(}[}@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^([>>^^^^^>^^^^>>>)()<<>]]]@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@[>^>[[)>^^^^^^^^^^^^^><<]<>><]@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@#>>^]]>^^^^^^^^^^^^^^>^^(>{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@(>>>({[}[^^^^^^^^^^^^^^>[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@(>><>>^^^^^^^^^^^^^^^>){%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@%<>]><>^^^^^^^^^^^^><]}}}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{<><])<><<^^^^^>)[}}{[[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{[>>^^^^^^^^>)[{}}}}}[}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%}[>>^^^^>){}}}}}}}}}}[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}#{}[}}}}}}}}}}}}}()%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@%@@@@@@@@@@@@@@}}}}{}}}}}}}}}}}}}]>>(%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{}}}{}}}}}}}}}}}})>>>]}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@%{{}}}}}}}}}}}}]<]<>>>>>[}%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}{[[}}}[)>>))>>>>>><[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}}}))(>>>>>[>>>>>>>><{@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}})>>[{<>>>^^()<<>>>>>><}@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@{)<<>><[}>>>>>[<](>>><<}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]<<(]>><}])[{#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ */