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.Input Format
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 Format
Print true if Sentence1 and Sentence2 are similar else print false.
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.
Example
Input
3 treat fight miss like train lost 4 treat catch train fight like catch miss lost
Output
true