Challenge: Friend Groups

Lab C++ Intermediate 20 points

With union-find, process q commands for n people: friend a b merges their groups; ask a b prints yes or no. Finally print Groups: <count>.

Input

Line 1: n q. Then q commands.

Output

One line per ask, then the group count.

Example

Input

5 5
friend 0 1
friend 2 3
ask 0 3
friend 1 3
ask 0 2

Output

no
yes
Groups: 2

Sample input available Sample output available

Editor

C++

Hints

find() follows parents to the leader.

Only reduce the group count when the leaders differ.

Solution explanation

Each operation is practically O(1) thanks to path compression.

Show solution

#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

vector<int> parent;

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

int main() {
    int n, q;
    cin >> n >> q;
    parent.resize(n);
    iota(parent.begin(), parent.end(), 0);
    int groups = n;
    while (q--) {
        string cmd;
        int a, b;
        cin >> cmd >> a >> b;
        int ra = find(a), rb = find(b);
        if (cmd == "friend") {
            if (ra != rb) { parent[rb] = ra; groups--; }
        } else {
            cout << (ra == rb ? "yes" : "no") << endl;
        }
    }
    cout << "Groups: " << groups << endl;
    return 0;
}

Output

Answer