提示: 欢迎访问OurACM平台。
Problem 2057 家谱

Accept: 154    Submit: 424
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

由于计划生育的实行,我们以及将来几代人都会是独生子女,即每对夫妇只会有一个孩子。那么给你XXXX年某人的一张树形族谱,你能指出其中任意两人的关系吗?

Input

输入数据第一行一个整数T表示有T组数据。

每组数据第一行一个正整数N (2 < N < 10000 ,且N为奇数),表示族谱中有N个家族成员。

接下来N/2行,每行三个整数a b c,表示a的父亲是b,a的母亲是c。数据保证所给的是一棵树,家族成员的编号为1到N。

接下来一行一个正整数M (0 < M < 100),表示有M询问。

接下来M行,每行两个整数x y (x!=y),表示询问x y的关系。

Output

对于每一个询问,输出一行。

若x是y的祖辈,则输出:

0 S

若y是x的祖辈,则输出:

1 S

若都不是以上两种情况,则输出:

Relative

前两种情况中的S表示一个由大写字母F和M组成的字符串,F表示父亲,M表示母亲,表示前者是后者的XXX。例如:

0 FMM 表示x是y的父亲的母亲的母亲。

1 MFMF 表示y是x的母亲的父亲的母亲的父亲。

以此类推。

Sample Input

1 9 3 6 7 5 8 9 1 2 3 2 4 5 3 8 2 1 7 3 9

Sample Output

0 MF 1 MM Relative

Source

FOJ有奖月赛-2011年11月

Submit  Back  Status  Discuss