In the year 2099, the people in Earth established diplomatic relations between aliens from Pegasus galaxy. The Pegasusan people developed a kind of language called Bean Language, the words of which are based on graphic symbols. In ancient times of Pegasus, the Pegasusan had no paper to write on.

So, they carved every word on one rigid bean, and they string these beans to form a sentence.

However, after the Pegasusan invented paper, the word of Bean Language differentiated into various handwritings. But handwritings of the same word have the same spots and edges relations. Like the two graphics in the fellow figure, they are the same word carved on bean and written on paper. Pegasusian can recognize the two forms are identical in no time, because they are so familiar with their own language.

Now, the Pegasusan provide us a dictionary of their words. The problem is that the people on Earth cannot identify the Bean Language words handwritings in one sight, especially when the word is more complex. So, that is your job to recognize the given two symbols are the same word or not.

The first line of input is an integer number, which is the number of cases, k. The following 3k lines contain k case.

In each case, the first line is an integer n, which is the number of spots of a bean word (2 <= n <= 1000). The second line is the connect relation of the word in Bean Language dictionary, and the third line is the connect relation of a word in handwriting.

Because all the spots in each word are labeled as 1, 2, ..., n, the connect relation is a list as u₁, v₁, u₂, v₂, ..., u_n-1, v_n-1. u_i and v_i denotes the two endpoints of one edge without direction, and the edges have no order.

For example the connect relation of the word in the figure above is 1 2 3 1 4 3 3 5 and 1 2 3 5 1 3 1 4. They are in fact the same word.

2
5
1 2 3 1 4 3 3 5
1 2 3 5 1 3 1 4
4
1 2 2 3 2 4
2 1 2 3 3 4

same
different