Challenge: Network Cables

Lab Java Intermediate 20 points

Computers 1 … n start unconnected. Commands: link a b plugs a cable between a and b; ask a b asks whether a and b can talk (through any chain of cables). Print yes or no for each ask. Use union-find.

Input

Line 1: n q. Then q commands.

Output

One answer per ask.

Example

Input

5 6
ask 1 2
link 1 2
link 3 4
ask 1 2
link 2 3
ask 1 4

Output

no
yes
yes

Sample input available Sample output available

Editor

Java

Hints

parent[i] = i at the start.

link: parent[find(a)] = find(b). ask: compare find(a) and find(b).

Solution explanation

With path compression each command is nearly O(1), however many cables are plugged in.

Show solution

import java.util.Scanner;

public class Main {
    static int[] parent;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), q = sc.nextInt();
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            String cmd = sc.next();
            int a = sc.nextInt(), b = sc.nextInt();
            if (cmd.equals("link")) parent[find(a)] = find(b);
            else sb.append(find(a) == find(b) ? "yes" : "no").append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer