DAY 1

PROBLEM 3

The visit

 

One consulting office is organized as follows:

All the clients are in a queue and the consulting  done is according to this queue, it is first in first out. The consultant for a client is determined according to the gender of the previous client, e.g. male (M) or female (F). For instance, the consultant Ci (i=1,2,..,N), (2<N<=40) which receives a client, consults the client and according to the his/her gender directs the next client to consultant Cj  if the present client is male, or to consultant Ck if the present client is female. Thus, this new consultant services the next client.

 

One clever client has discovered that in a case it is possible to be in a queue position that regardless of the consultant that begins the consulting, this client to be treated by a fixed consultant Cm.

You have to write a program that discovers if this is possible and if so, to find the minimal length queue which ends with this client and the consultant, which will consult this client.

On the contrary, if such a queue does not exist, your program will write the message: ’impossible’.

The official consultants that conduct the consulting are represented by integers 1,2,..,N.

Input file

Input text file c:\day1\problem3\visit.in contains in the first line an integer N, (2<N<=40),  the number of consultants in this office.

In the N following lines, are three integers per line. The first integer represents the consultant who is consulting, the second integer is the consultant who continues consulting in the case when the client being consulted was a female one,  whereas the third integer represents the consultant who will continue consulting if the client being consulted was e male one.

Output file

Output text file c:\day1\problem3\visit.out will contain three lines if such a queue exists, or one line if not.

In the case this queue exists the first line of the file will contains the length of the queue, the second line contains  a string of characters F,M that represents the queue, the third line contains the consultant who will consult the client.

In case this queue is impossible, the output file visit.out will have one line with string ‘Impossible’

Executable file c:\day1\problem3\visit.exe.

Exemple 1

Input File:

visit.in

5

1          2            4

2          4            1

3          2            3

4          1            4

5          3            5

 

Output File

visit.out

4

FFMM

4

 

 

 

Exemple 2.

Input file

visit.in

 

4

1          4            2

2          3             1

3          1            4

4          2            3

 

Output file.

visit.out

Impossible

 

Time limit per test 5 sec.