Under construction

Still being built. Things may change

Group Division

Interview

Time limit1sMemory limit1024 MB

Summary
Given students and their friend pairs, find the largest number of groups where every friend pair stays together, which equals the count of friend clusters.
Level

Easy3 of 10

Topics
Union-find, Graph, Hash map
Solved
No attempts yet

Problem

During a school trip, the students must be divided into groups. Naturally, the students want to be in the same group as their friends. Given the name of each student and which students are friends with each other, write a program that computes the maximum number of groups the students can be divided into while every student gets the group they want.

Input

The first line contains an integer nn (2≤n≤1002 \le n \le 100), the number of students on the trip. The next nn lines each contain one student's name. Each name is between 1 and 20 characters long and contains only the letters A-Z. All names are different.

The next line contains an integer mm (1≤m≤49501 \le m \le 4950), the number of friend pairs. The last mm lines each contain a friend pair as two names separated by a space.

Output

Print one line with one integer: the maximum number of groups the students can be divided into.

Examples1

  1. Example 1

    Input
    6
KALLE
MAJA
SARA
SVEN
HUGO
ANNA
3
KALLE ANNA
MAJA ANNA
SARA HUGO
    Expected output
    3