#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Node {
vector<int> parents; // Item pos
vector<int> children;
Node* root = nullptr;
int depth = -1;
};
struct Item {
Node* node = nullptr;
int coinNum = -1;
};
int N,M,V;
vector<Item> items;
int dfs(bool goUp, bool setDepth, Node* node, int depth, Node* root) {
if (goUp && !node->parents.empty()) { // go up to parent
for (const auto& parent : node->parents) {
dfs(true, false, items[parent].node, 1, nullptr);
}
} else if (!setDepth) { // find N long path (if you find val with depth set go up and set?)
if (depth == N) return N;
int maxD = 0;
for (const auto& child : node->children) {
maxD = max(maxD, dfs(false, false, items[child].node, depth+1, nullptr));
}
if (node->parents.empty() && maxD == N) {
node->depth = 1;
for (const auto& child : node->children) {
dfs(false, true, items[child].node, node->depth + 1, node);
}
}
if (maxD == N) return N;
} else { // set depth
node->depth = depth;
for (const auto& child : node->children) {
dfs(false, true, items[child].node, node->depth + 1, root);
}
}
return 0;
}
int main() {
scanf("%d %d %d",&N,&M,&V);
items.resize(M, Item{nullptr, -1});
for (int i = 0; i < V; i++) {
int A,B; char C; scanf("%d %c %d", &A, &C,&B);
A--;
B--;
if (!items[A].node) items[A].node = new Node{{}, {}, nullptr, -1};
if (!items[B].node) items[B].node = new Node{{}, {}, nullptr, -1};
if (C == '=') {
for (int i = 0; i < items[B].node->parents.size(); i++) {
items[A].node->parents.push_back(items[B].node->parents[i]);
}
for (int i = 0; i < items[B].node->children.size(); i++) {
items[A].node->children.push_back(items[B].node->children[i]);
}
items[B].node = items[A].node;
} else { // A < B
items[B].node->parents.push_back(A);
items[A].node->children.push_back(B);
}
}
for (int i = 0; i < items.size(); i++) {
if (items[i].node && items[i].node->depth == -1) {
dfs(true, false, items[i].node, 1, nullptr);
}
}
for (int i = 0; i < items.size(); i++) {
int coinNum = -1;
if (items[i].node) coinNum = items[i].node->depth;
if (coinNum == -1) printf("?\n");
else printf("K%d\n", coinNum);
}
// dfs -> go to all parents until empty -> then start dfs and get max of all children and see if == N -> if yes then go to all children and set depth
// if during dfs -> depth of a child is set -> then set all other depths based on it
// iterate over items and start dfs (if somewhere depth != -1 -> go up and set everything accordingly)
// at end if depth == -1 -> ? otherwise depth = Coin num
return 0;
}
