Challenge: Friend Groups

Lab Python Intermediate 20 points

There are n people (0 … n − 1). Process q commands with union-find: friend a b makes a and b friends (their groups merge); ask a b prints yes if they're in the same group, otherwise no. At the end print Groups: <count>.

Input

Line 1: n q. Then q commands.

Output

One line per ask, then the number of groups.

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

Python

Hints

find() follows parents up to the leader.

friend: if the two leaders differ, point one at the other and reduce the group count.

Solution explanation

Counting a merge only when the leaders differ keeps the group count right even for repeated friendships.

Show solution

n, q = map(int, input().split())
parent = list(range(n))


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


groups = n
for _ in range(q):
    cmd, a, b = input().split()
    ra, rb = find(int(a)), find(int(b))
    if cmd == "friend":
        if ra != rb:
            parent[rb] = ra
            groups -= 1
    else:
        print("yes" if ra == rb else "no")
print("Groups:", groups)

Output

Answer