Equal or Not Equal
Source: aizu

Equal or Not Equal
Problem Statement

There are $N$ integer variables $a_1, ..., a_N$. All the initial values are unspecified. You have to process $M$ events in order, each of which is an observation event, a change event or an inquiry event.

One kind of an observation event has the format,

1 $x$ $y$


which represents that it is observed that $a_x$ and $a_y$ are equal. In other words, after this event it is guaranteed that these two variables have the same value unless there is a change event for either variable.

The other kind of an observation event has the format,

2 $x$ $y$


which represents that it is observed that $a_x$ and $a_y$ are not equal.
A change event has the format,

3 $x$


which represents that the value of $a_x$ changes to a different integer.
Finally, an inquiry event has the format,

4 $x$ $y$


which asks whether $a_x$ and $a_y$ are equal. If it can be proven from all the past events that $a_x$ and $a_y$ are equal, you have to print Yes. Similarly, if it can be proven that $a_x$ and $a_y$ are not equal, you have to print No. If neither can be proven, you have to print Unknown.

Input

The input consists of a single test case of the following format, where all values in the input are integers.

$N$ $M$
$event_1$
$\vdots$
$event_M$


The integer $N$ is the number of variables ($1 \leq N \leq 10^6$). The integer $M$ is the number of events ($1 \leq M \leq 500,000$). $M$ events are given in chronological order. The format of each event is explained above. In an observation event or an inquiry event, it is guaranteed that $1 \leq x < y \leq N$. In a change event it is guaranteed that $1 \leq x \leq N$.

At any point, it is guaranteed that there is at least one assignment to all $N$ variables that contradicts none of the given information.

Output

For each inquiry event, print Yes, No or Unknown followed by a newline.

Sample Input
4 11
1 1 2
4 1 2
2 3 4
4 3 4
4 1 3
1 1 3
4 1 3
4 1 4
3 1
4 1 3
4 1 4

Sample Output
Yes
No
Unknown
Yes
No
No
Unknown


C++ solution:
// AOJ #3647 Equal or Not Equal
// 2025.4.20

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

#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

int Cin() {
    int n = 0; int c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

void Couts(const string &s) {
    for (char c : s) pc(c);
    pc('\n');
}

int N, M, id;
vector<int> p, rk, cur;
vector<unordered_set<int>> nei;

int findp(int x) {
    return p[x]==x ? x : p[x]=findp(p[x]);
}

void merge_nei(int r, int s){
    if(nei[s].empty()) return;
    for(int v : nei[s]){
        nei[r].insert(v);
        nei[v].erase(s);
        nei[v].insert(r);
    }
    nei[s].clear();
}

void unite(int x, int y){
    x = findp(x);
    y = findp(y);
    if(x == y) return;
    if(rk[x] < rk[y]) swap(x,y);
    p[y] = x;
    if(rk[x] == rk[y]) rk[x]++;
    merge_nei(x, y);
}

int main(){
    N = Cin(), M = Cin();
    id = N;
    int SZ = N + M + 5;

    p.resize(SZ);
    rk.assign(SZ, 0);
    cur.resize(N+1);
    nei.assign(SZ, unordered_set<int>());

    for(int i = 1; i < SZ; i++) p[i] = i;
    for(int i = 1; i <= N; i++) cur[i] = i;

    for(int i = 0; i < M; i++){
        int t = Cin() & 0xf, gc();
        int x, y;
        if(t == 1){
            x = Cin(), y = Cin();
            unite(cur[x], cur[y]);
        } else if(t == 2){
            x = Cin(), y = Cin();
            int rx = findp(cur[x]), ry = findp(cur[y]);
            if(rx != ry){
                nei[rx].insert(ry);
                nei[ry].insert(rx);
            }
        } else if(t == 3){
            x = Cin();
            int old = cur[x];
            cur[x] = ++id;
            p[id]    = id;
            rk[id]   = 0;
            int rx = findp(old), ry = findp(id);
            if(rx != ry){
                nei[rx].insert(ry);
                nei[ry].insert(rx);
            }
        } else {
            x = Cin(), y = Cin();
            int rx = findp(cur[x]), ry = findp(cur[y]);
            if(rx == ry) Couts("Yes");
            else if(nei[rx].count(ry)) Couts("No");
            else Couts("Unknown");
        }
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1<<20), 1<<20) // Large buffer for big inputs

	// Read first line (N and M)
	scanner.Scan()
	firstLine := scanner.Text()
	parts := strings.Fields(firstLine)
	N, _ := strconv.Atoi(parts[0])
	M, _ := strconv.Atoi(parts[1])

	// Initialize data structures
	id := N
	SZ := N + M + 5 // Sufficient size for all possible nodes

	p := make([]int, SZ)    // Parent array for Union-Find
	rk := make([]int, SZ)    // Rank array for Union-Find
	cur := make([]int, N+1) // Current version of each variable
	nei := make([]map[int]bool, SZ) // Neighbors (inequality relationships)

	// Initialize Union-Find and current versions
	for i := 1; i < SZ; i++ {
		p[i] = i
		nei[i] = make(map[int]bool)
	}
	for i := 1; i <= N; i++ {
		cur[i] = i
	}

	// Find with path compression
	find := func(x int) int {
		for p[x] != x {
			p[x] = p[p[x]] // Path compression
			x = p[x]
		}
		return x
	}

	// Merge neighbors when combining sets
	mergeNeighbors := func(r, s int) {
		for v := range nei[s] {
			nei[r][v] = true
			delete(nei[v], s)
			nei[v][r] = true
		}
		nei[s] = make(map[int]bool) // Clear the merged set's neighbors
	}

	// Union operation with rank
	unite := func(x, y int) {
		x = find(x)
		y = find(y)
		if x == y {
			return
		}
		if rk[x] < rk[y] {
			x, y = y, x
		}
		p[y] = x
		if rk[x] == rk[y] {
			rk[x]++
		}
		mergeNeighbors(x, y)
	}

	// Process each event
	for i := 0; i < M; i++ {
		scanner.Scan()
		line := scanner.Text()
		parts := strings.Fields(line)
		t, _ := strconv.Atoi(parts[0])

		switch t {
		case 1: // Equality observation (a_x == a_y)
			x, _ := strconv.Atoi(parts[1])
			y, _ := strconv.Atoi(parts[2])
			unite(cur[x], cur[y])
		case 2: // Inequality observation (a_x != a_y)
			x, _ := strconv.Atoi(parts[1])
			y, _ := strconv.Atoi(parts[2])
			rx := find(cur[x])
			ry := find(cur[y])
			if rx != ry {
				nei[rx][ry] = true
				nei[ry][rx] = true
			}
		case 3: // Change event (a_x changes value)
			x, _ := strconv.Atoi(parts[1])
			old := cur[x]
			id++
			cur[x] = id
			p[id] = id
			rk[id] = 0
			nei[id] = make(map[int]bool)
			rx := find(old)
			ry := find(id)
			if rx != ry {
				nei[rx][ry] = true
				nei[ry][rx] = true
			}
		case 4: // Inquiry (are a_x and a_y equal?)
			x, _ := strconv.Atoi(parts[1])
			y, _ := strconv.Atoi(parts[2])
			rx := find(cur[x])
			ry := find(cur[y])
			if rx == ry {
				fmt.Println("Yes")
			} else if nei[rx][ry] {
				fmt.Println("No")
			} else {
				fmt.Println("Unknown")
			}
		}
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    static int[] parent;
    static int[] rank;
    static int[] current;
    static List<Set<Integer>> neighbors;
    static int id;

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) return;
        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
            mergeNeighbors(yRoot, xRoot);
        } else if (rank[xRoot] > rank[yRoot]) {
            parent[yRoot] = xRoot;
            mergeNeighbors(xRoot, yRoot);
        } else {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
            mergeNeighbors(xRoot, yRoot);
        }
    }

    static void mergeNeighbors(int r, int s) {
        if (neighbors.get(s).isEmpty()) return;
        for (int v : neighbors.get(s)) {
            neighbors.get(r).add(v);
            neighbors.get(v).remove(s);
            neighbors.get(v).add(r);
        }
        neighbors.get(s).clear();
    }

    public static void main(String[] args) {
        FastReader fr = new FastReader();
        PrintWriter out = new PrintWriter(System.out);

        int N = fr.nextInt();
        int M = fr.nextInt();
        id = N;
        int SZ = N + M + 5;

        parent = new int[SZ];
        rank = new int[SZ];
        current = new int[N + 1];
        neighbors = new ArrayList<>(SZ);

        for (int i = 0; i < SZ; i++) {
            parent[i] = i;
            neighbors.add(new HashSet<>());
        }
        for (int i = 1; i <= N; i++) {
            current[i] = i;
        }

        for (int i = 0; i < M; i++) {
            int t = fr.nextInt();
            if (t == 1) {
                int x = fr.nextInt();
                int y = fr.nextInt();
                union(current[x], current[y]);
            } else if (t == 2) {
                int x = fr.nextInt();
                int y = fr.nextInt();
                int rx = find(current[x]);
                int ry = find(current[y]);
                if (rx != ry) {
                    neighbors.get(rx).add(ry);
                    neighbors.get(ry).add(rx);
                }
            } else if (t == 3) {
                int x = fr.nextInt();
                int old = current[x];
                current[x] = ++id;
                parent[id] = id;
                rank[id] = 0;
                int rx = find(old);
                int ry = find(current[x]);
                if (rx != ry) {
                    neighbors.get(rx).add(ry);
                    neighbors.get(ry).add(rx);
                }
            } else {
                int x = fr.nextInt();
                int y = fr.nextInt();
                int rx = find(current[x]);
                int ry = find(current[y]);
                if (rx == ry) {
                    out.println("Yes");
                } else if (neighbors.get(rx).contains(ry)) {
                    out.println("No");
                } else {
                    out.println("Unknown");
                }
            }
        }
        out.flush();
    }
}

JavaScript solution:
const fs = require('fs');

function main() {
    const input = fs.readFileSync(0, 'utf-8').split('\n');
    let ptr = 0;
    const [N, M] = input[ptr++].trim().split(' ').map(Number);
    
    let id = N;
    const SZ = N + M + 5;
    
    const p = new Array(SZ);
    const rk = new Array(SZ).fill(0);
    const cur = new Array(N + 1);
    const nei = new Array(SZ);
    
    for (let i = 1; i < SZ; i++) {
        p[i] = i;
        nei[i] = new Set();
    }
    for (let i = 1; i <= N; i++) cur[i] = i;
    
    function findp(x) {
        if (p[x] !== x) {
            p[x] = findp(p[x]);
        }
        return p[x];
    }
    
    function mergeNei(r, s) {
        if (nei[s].size === 0) return;
        for (const v of nei[s]) {
            nei[r].add(v);
            nei[v].delete(s);
            nei[v].add(r);
        }
        nei[s].clear();
    }
    
    function unite(x, y) {
        x = findp(x);
        y = findp(y);
        if (x === y) return;
        if (rk[x] < rk[y]) [x, y] = [y, x];
        p[y] = x;
        if (rk[x] === rk[y]) rk[x]++;
        mergeNei(x, y);
    }
    
    const output = [];
    
    for (let i = 0; i < M; i++) {
        const line = input[ptr++];
        if (!line) continue;
        const parts = line.trim().split(' ');
        const t = parseInt(parts[0], 10);
        if (t === 1) {
            const x = parseInt(parts[1], 10);
            const y = parseInt(parts[2], 10);
            unite(cur[x], cur[y]);
        } else if (t === 2) {
            const x = parseInt(parts[1], 10);
            const y = parseInt(parts[2], 10);
            const rx = findp(cur[x]);
            const ry = findp(cur[y]);
            if (rx !== ry) {
                nei[rx].add(ry);
                nei[ry].add(rx);
            }
        } else if (t === 3) {
            const x = parseInt(parts[1], 10);
            const old = cur[x];
            cur[x] = ++id;
            p[id] = id;
            rk[id] = 0;
            nei[id] = new Set();
            const rx = findp(old);
            const ry = findp(id);
            if (rx !== ry) {
                nei[rx].add(ry);
                nei[ry].add(rx);
            }
        } else if (t === 4) {
            const x = parseInt(parts[1], 10);
            const y = parseInt(parts[2], 10);
            const rx = findp(cur[x]);
            const ry = findp(cur[y]);
            if (rx === ry) {
                output.push("Yes");
            } else if (nei[rx].has(ry)) {
                output.push("No");
            } else {
                output.push("Unknown");
            }
        }
    }
    
    console.log(output.join('\n'));
}

main();

Python solution:
import sys
from sys import stdin
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    parent = []
    rank = []
    current = []
    nei = defaultdict(set)  # nei[root] stores roots that are known to be unequal to root

    max_id = N + M + 5
    parent = list(range(max_id))
    rank = [0] * max_id
    current = list(range(N + 1))  # 1-based
    id_counter = N

    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root == v_root:
            return
        if rank[u_root] > rank[v_root]:
            parent[v_root] = u_root
            # Merge the nei sets
            for x in list(nei[v_root]):
                nei[u_root].add(x)
                nei[x].discard(v_root)
                nei[x].add(u_root)
            nei[v_root].clear()
        else:
            parent[u_root] = v_root
            if rank[u_root] == rank[v_root]:
                rank[v_root] += 1
            # Merge the nei sets
            for x in list(nei[u_root]):
                nei[v_root].add(x)
                nei[x].discard(u_root)
                nei[x].add(v_root)
            nei[u_root].clear()

    output = []
    for _ in range(M):
        event = input[ptr]
        if event == '1':
            ptr += 1
            x = int(input[ptr])
            ptr += 1
            y = int(input[ptr])
            ptr += 1
            # Merge current[x] and current[y]
            union(current[x], current[y])
        elif event == '2':
            ptr += 1
            x = int(input[ptr])
            ptr += 1
            y = int(input[ptr])
            ptr += 1
            # Mark current[x] and current[y] as not equal
            x_root = find(current[x])
            y_root = find(current[y])
            if x_root != y_root:
                nei[x_root].add(y_root)
                nei[y_root].add(x_root)
        elif event == '3':
            ptr += 1
            x = int(input[ptr])
            ptr += 1
            # Change current[x] to a new id
            old_id = current[x]
            id_counter += 1
            new_id = id_counter
            current[x] = new_id
            parent[new_id] = new_id
            rank[new_id] = 0
            # Mark old and new as not equal
            old_root = find(old_id)
            new_root = find(new_id)
            if old_root != new_root:
                nei[old_root].add(new_root)
                nei[new_root].add(old_root)
        elif event == '4':
            ptr += 1
            x = int(input[ptr])
            ptr += 1
            y = int(input[ptr])
            ptr += 1
            x_root = find(current[x])
            y_root = find(current[y])
            if x_root == y_root:
                output.append("Yes")
            else:
                if y_root in nei[x_root]:
                    output.append("No")
                else:
                    output.append("Unknown")
    print('\n'.join(output))

if __name__ == '__main__':
    main()

Ruby solution:
require 'set'

def main
  input = $stdin.read.split
  ptr = 0
  n = input[ptr].to_i; ptr += 1
  m = input[ptr].to_i; ptr += 1

  id = n
  sz = n + m + 5

  p = (0...sz).to_a
  rk = Array.new(sz, 0)
  cur = (1..n).to_a
  nei = Array.new(sz) { Set.new }

  find = lambda do |x|
    while p[x] != x
      p[x] = p[p[x]]
      x = p[x]
    end
    x
  end

  merge_nei = lambda do |r, s|
    unless nei[s].empty?
      nei[s].each do |v|
        nei[r].add(v)
        nei[v].delete(s)
        nei[v].add(r)
      end
      nei[s].clear
    end
  end

  unite = lambda do |x, y|
    x = find.call(x)
    y = find.call(y)
    return if x == y

    if rk[x] < rk[y]
      x, y = y, x
    end
    p[y] = x
    rk[x] += 1 if rk[x] == rk[y]
    merge_nei.call(x, y)
  end

  m.times do
    t = input[ptr].to_i; ptr += 1
    if t == 1
      x = input[ptr].to_i; ptr += 1
      y = input[ptr].to_i; ptr += 1
      unite.call(cur[x - 1], cur[y - 1])
    elsif t == 2
      x = input[ptr].to_i; ptr += 1
      y = input[ptr].to_i; ptr += 1
      rx = find.call(cur[x - 1])
      ry = find.call(cur[y - 1])
      if rx != ry
        nei[rx].add(ry)
        nei[ry].add(rx)
      end
    elsif t == 3
      x = input[ptr].to_i; ptr += 1
      old = cur[x - 1]
      id += 1
      cur[x - 1] = id
      p[id] = id
      rk[id] = 0
      rx = find.call(old)
      ry = find.call(id)
      if rx != ry
        nei[rx].add(ry)
        nei[ry].add(rx)
      end
    else
      x = input[ptr].to_i; ptr += 1
      y = input[ptr].to_i; ptr += 1
      rx = find.call(cur[x - 1])
      ry = find.call(cur[y - 1])
      if rx == ry
        puts "Yes"
      elsif nei[rx].include?(ry)
        puts "No"
      else
        puts "Unknown"
      end
    end
  end
end

main