#6131. 「2017 山东三轮集训 Day1」Fiend

内存限制:233 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

因为成功解决了顾客的排序问题,滋滋国的首席排序使 Lyra 一夜成名,远方的魔鬼因为不会排序而困恼了几百年,听说 Lyra 的事迹,连夜赶来掳走了 Lyra,作为滋滋国的勇士,你前去营救 Lyra 的时候,魔鬼要和你玩一个游戏,若你赢了魔鬼便可以带走 Lyra,若你输给了魔鬼就会被魔鬼吃掉,平局则是你会被魔鬼嘿嘿嘿。

游戏是这样的,没一轮你和魔鬼同时选择一个 1 \sim n 的排列 P ,必须满足 L_i \leq P_i \leq R_i(1 \leq i \leq n) ,同时,你选择的排列逆序对数必须是偶数,而魔鬼选择的排列逆序对数必须是奇数(显然你的排列和魔鬼的排列不可能相同)。每一轮选择的排列不能和之前出现过的排列相同,先无法选择排列的输,若双方同时无法选择排列则是和局。

你需要对于给定的 n, L_i, R_i ,判断游戏的结果。

输入格式

第一行一个正整数 T 表示数据组数。
对于每组数据,第一行一个正整数 n ,接下来 n 行,每行两个整数 L_i, R_i

输出格式

对于每组数据输出一行一个字母,Y 表示你会赢得游戏,F 表示魔鬼会赢得游戏,D 表示平局。

样例

样例输入 1

3
1
1 1
2
2 2
1 1
2
1 2
1 2

样例输出 1

Y
F
D

样例输入 2

见「附加文件」中的 ex_fiend2.in

样例输出 2

见「附加文件」中的 ex_fiend2.out

数据范围与提示

对于全部数据, 1 \leq T \leq 500; 1 \leq n \leq 100,000; 1 \leq \sum n \leq 1500,000; 1 \leq L_i \leq R_i \leq n

子任务 1(5 分) n \leq 8
子任务 2(15 分) n \leq 15
子任务 3(15 分) n \leq 75
子任务 4(15 分) n \leq 250
子任务 5(20 分) n \leq 650
子任务 6(30 分) n \leq 100,000