Polish version    English version  
  History of OI -> VIII OI 2000/2001

 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
Stage III - results
Stage II - results
Stage I - results
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
VIII Olimpiada Informatyczna 2000/2001

Task: PCH
Author: Marcin Sawicki
Wandering flea trainers

III stage contest, the trial day  

Byteland is known for wandering flea trainers. Tamed fleas are taught to dance. They make precise leaps in the rhythm of music. On the table the trainer puts in a row numbered coins, but it's not assumed that they are arranged in any specific order. On each coin there is an inscription of the form "i->j"; i is the number of this coin and j is the number of the coin on which a flea should leap if it sits on this coin. Then the trainer puts one flea on each coin and turns on the music. The fleas, while dancing, follow the rhythm of the music; i.e. at each beat of music each flea leaps directly to the coin with number equal to the j-number written on the coin it is sitting on. During the dance it may happen that many fleas sit on the same coin. In this case they continue their performance together. Let's assume that we have n coins and n fleas. As soon as we say what numbers are written on the coins 1,2,...,n, we will have the performance fully determined. However, two different sets of coins may give the same performance, if only we arrange them in appropriate order.


Let us consider the performance on three coins. If the leaps are performed in the following way: from the first coin to the second one, from the second coin to the third one, from the third coin to the first one (we denote this: 1->2, 2->3, 3->1); then the fleas will dance in a circle and no two of them will ever meet on one coin. For example, the dance 1->2, 2->3, 3->3 is different, because it will make all the fleas meet on the third coin after two beats of music and it will make them jump only on the third coin forever.

However,  the sets 1->2, 2->3, 3->2, 4->4 and 1->1, 2->3, 3->2, 4->3 are of the same type. If you put these coins in the row - the first set from left to right and the second from right to left - you would see the same performance.


The spectators are discontent if the fleas perform in the same way for the second time. Hence there is needed a program which:
  • reads from the text file PCH.IN the number of test cases,
  • for each case, reads from the file PCH.IN the description of two sets of coins and verifies, whether or not, one can arrange the coins from these sets on the table in such a way, that fleas would give the same performance on both sets of coins,
  • writes the result into the text file PCH.OUT.


In the first line of the text file PCH.IN there is written one integer d equal to the number of test cases, 1<=d<=100. In the following 3*d lines the test cases are described -- each case occupies three consecutive lines. The first of  these three contains one integer n, 1<=n<=2 000, equal to the number of coins. Each of the remaining two lines is a description of a set of n coins in a form of n integers from the interval 1...n, separated by single spaces; the i-th integer denotes the number of a coin that flea must leap to when it seats on the i-th coin.


For each of the test cases from the file PCH.IN your program should write into the text file PCH.OUT exactly one line containing exactly one letter:

  • "T" -- if one can arrange on a table the coins from both sets in a way, that makes fleas perform in the same way,
  • "N" -- otherwise. 


For the input file PCH.IN:

2 3 1
2 3 3
2 3 2 4
1 3 2 3
the correct answer is the output file PCH.OUT:

Print friendly version