Sentence Similarity
easy
Given two sentences sentence1 and sentence2 each represented as a string array and given a 2d array of string pairs where each row contains two words {x,y} indicating that the word x and y are similar. Return true if sentence1 and sentence2 are similar, or false if they are not similar. Two sentences are similar if they have the same length and sentence1[i] and sentences2[i] are similar. Note: Similarity relation is transitive.
Constraints
1 <= sentence1.length, Sentence2.length <= 100000 1 <= sentence1[i].length, sentence2[i].length <= 20 sentence1[i] and sentence2[i] consist of lower-case and upper-case English letters.
Format
Input
First line contains an integer denoting the sentence length. Second line contaions the words of sentence1 separated by space. Third line contains the words of sentence2 separated by space. Fourth line contains an integer m denoting number of pairs. Each of next m lines contains 2 words separated by space which are similar.
Output
Print true if Sentence1 and Sentence2 are similar else print false.
Example
Sample Input
3
treat fight miss
like train lost
4
treat catch
train fight
like catch
miss lost
Sample Output
true