aoj1330:Never_Wait_for_Weights.cpp

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UF{
    vint par,sz;
    vector<set<int>>st;
    vint dif;
    void init(int n){
        par=sz=dif=vint(n);
        st=vector<set<int>>(n);
        rep(i,n){
            par[i]=i;
            sz[i]=1;
            dif[i]=0;
            st[i].insert(i);
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void update(int a,int b,int w){
        int x=find(a),y=find(b);
        if(x==y)return;
        if(sz[x]>sz[y]){
            swap(x,y);
            swap(a,b);
            w*=-1;
        }
        
        int d=dif[b]-dif[a];
        each(it,st[x]){
            int v=*it;
            dif[v]+=d-w;
            st[y].insert(v);
        }
        sz[y]+=sz[x];
        par[x]=y;
    }
    int query(int a,int b){
        int x=find(a),y=find(b);
        if(x!=y)return 1001001001;
        return dif[b]-dif[a];
    }
};

signed main(){

    int N,Q;
    while(scanf("%lld%lld",&N,&Q),N||Q){
        UF uf;uf.init(N);
        rep(i,Q){
            char c;
            scanf(" %c",&c);
            if(c=='!'){
                int a,b,w;
                scanf("%lld%lld%lld",&a,&b,&w);
                a--;b--;
                uf.update(a,b,w);
            }
            else{
                int a,b;
                scanf("%lld%lld",&a,&b);
                a--;b--;
                int tmp=uf.query(a,b);
                if(tmp==1001001001)puts("UNKNOWN");
                else printf("%lld\n",tmp);
            }
        }
    }
    return 0;
}