import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
class Edge {
int start, end;
int weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
class Node<T> extends ArrayList<T> {
public static Node[] Tree;
public int nodeNo;
public int parentNo;
public int rank;
public void makeSet(int x) {
nodeNo = x;
parentNo = x;
rank = 0;
}
public int findSet() {
Stack<Integer> nodeStack = new Stack<>();
nodeStack.add(nodeNo); // 검색 노드 조건
Node moveNode = Tree[nodeNo];
while (moveNode.nodeNo != moveNode.parentNo) { // 부모 노드 조건
moveNode = Tree[moveNode.parentNo];
nodeStack.add(parentNo);
}
if (nodeStack.size() > 1) { // 찾은 부모가 있다면
int represent = moveNode.nodeNo;
while (!nodeStack.isEmpty()) { // 부모노드를 가르키도록
Tree[nodeStack.pop()].parentNo = represent;
}
}
return moveNode.nodeNo;
}
public void unionSet(Node<T> node) {
Node first = Tree[this.nodeNo];
Node second = Tree[node.nodeNo];
int f = first.findSet();
int s = second.findSet();
if (f == s) {
return;
}
first = Tree[f];
second = Tree[s];
if (first.rank > second.rank) {
second.parentNo = first.nodeNo;
} else {
first.parentNo = second.nodeNo;
if (this.rank == node.rank) {
node.rank++;
}
}
}
}
class Solution {
static int DATA_SIZE;
static Node<Edge>[] tree;
static Boolean isFound;
static int[] visited;
static int[] distance;
static boolean Debug = true;
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "input (29).txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in));
}
StringTokenizer st;
int start, end, weight;
int testNo = Integer.parseInt(br.readLine());
for (int T = 1; T <= 6; T++) {
st = new StringTokenizer(br.readLine());
int nodeNum = Integer.parseInt(st.nextToken());
int taskNum = Integer.parseInt(st.nextToken());
StringBuffer sb = new StringBuffer();
System.out.print(String.format("#%d", T, nodeNum, taskNum));
log("");
tree = new Node[nodeNum + 1];
visited = new int[nodeNum + 1];
distance = new int[nodeNum + 1];
Node.Tree = tree;
for (int i = 0; i < tree.length; i++) {
tree[i] = new Node<Edge>();
tree[i].makeSet(i);
}
// [방법2]
ArrayList<Integer> representList = new ArrayList<>();
for (int i = 0; i < taskNum; i++) {
st = new StringTokenizer(br.readLine());
switch (st.nextToken()) {
case "!":
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
weight = Integer.parseInt(st.nextToken());
tree[start].add(new Edge(start, end, weight));
tree[end].add(new Edge(end, start, -1 * weight));
tree[start].unionSet(tree[end]);
break;
case "?":
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
// findPath(start, end);
int a = tree[start].findSet();
int b = tree[end].findSet();
if (a == b) {
// [방법2 ] 무게의 상대값을 기록하여 재활용하기
// if(!representList.contains((Integer) a)) {
// representList.add(a);
// visited = new int[nodeNum + 1];
// distance = new int[nodeNum + 1];
// }
int w_end = findWeight(end);
int w_start = findWeight(start);
int answer = w_end - w_start;
sb.append(String.format(" %d", answer));
} else {
sb.append(" UNKOWN");
}
break;
}
}
System.out.println(sb.toString());
}
}
private static int findWeight(int nodeNo) {
if (visited[nodeNo] == 1) {
log(String.format("3. distance[%d] = %d", nodeNo, distance[nodeNo]));
return distance[nodeNo];
}
// 연결된 노드를 찾는다.
int subParent = 0;
Queue<Integer> que = new LinkedList();
que.add(nodeNo);
Stack<Integer> visiting = new Stack();
while (!que.isEmpty()) {
int reStart = que.poll();
log(String.format("nodeNo:%d reStart: %d", nodeNo, reStart));
for (Edge line : tree[reStart]) {
log(String.format("visited[%d] = %d", line.end, visited[line.end]));
if (visited[line.end] == 1 || line.end == tree[nodeNo].parentNo) {
// 무게가 기록된 연결된 노드를 찾음 || 부모노드
subParent = line.end;
break;
}
que.add(line.end);
visited[line.end] = 1;
visiting.add(line.end);
}
}
for (int i : visiting) {
visited[i] = 0;
}
que = new LinkedList();
que.add(subParent);
log("subParent 진입: " + subParent);
while (!que.isEmpty()) {
int reStart = que.poll();
for (Edge line : tree[reStart]) {
if (visited[line.end] == 1) {
continue;
}
// que.add(line.end);
que.add(line.end);
visited[line.end] = 1;
distance[line.end] = distance[line.start] + line.weight;
log(String.format("2. distance[%d] = %d", line.end, distance[line.end]));
if (line.end == nodeNo) {
return distance[line.end];
}
}
}
return -1;
}
private static void log(String input) {
if (true) {
System.out.println(input);
}
}
}