가격 차이 기록 검증

문제

온라인 쇼핑몰에는 1번부터 N번까지 번호가 붙은 N개의 상품이 있다. 각 상품의 정확한 가격은 알 수 없고, 담당자가 남긴 M개의 기록만 시간 순서대로 주어진다. 기록은 두 종류이다.\n'1 a b w' 형식은 a번 상품의 가격이 b번 상품의 가격보다 정확히 w원 비싸다는 새로운 주장이다. w는 음수일 수도 있고 0일 수도 있다. 이 주장이 앞서 적용된 주장들로부터 이미 알 수 있는 사실과 모순되지 않으면 적용한다. 이미 두 상품의 가격 차이를 알 수 있는데 그 값이 w와 다르면 모순이므로 이 기록은 무시하고 무시된 기록의 수에 센다. 아직 가격 차이를 알 수 없는 두 상품에 대한 주장은 항상 적용한다. a와 b가 같은 상품이면 w가 0일 때만 모순이 아니다.\n'2 a b' 형식은 이 시점까지 적용된 주장들만으로 a번 상품의 가격에서 b번 상품의 가격을 뺀 값을 알 수 있는지 묻는 질문이다. 알 수 있으면 그 값을 출력하고, 알 수 없으면 UNKNOWN을 출력한다. a와 b가 같은 상품이면 0이다.\n기록을 순서대로 처리하면서 질문마다 답을 출력하고, 마지막에 무시된 기록의 수를 출력하시오.

입력

첫 줄에 N, M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000, 1 ≤ M ≤ 200000) 다음 M줄에 기록이 시간 순서대로 주어진다. 주장은 '1 a b w' (1 ≤ a, b ≤ N, -10^9 ≤ w ≤ 10^9), 질문은 '2 a b' (1 ≤ a, b ≤ N) 형식이다.

출력

질문이 나온 순서대로 답을 한 줄에 하나씩 출력한다. 답은 정수 또는 UNKNOWN이다. 마지막 줄에 무시된 기록의 수를 출력한다.

4 7
1 1 2 5
1 2 3 -2
2 1 3
2 1 4
1 1 3 4
1 3 4 7
2 4 1

3
UNKNOWN
-10
1

2 4
1 1 1 0
1 1 1 3
2 2 2
2 1 2

0
UNKNOWN
1

출처: Devin.KR 자체 제작