305575: CF1056H. Detect Robots
Memory Limit:1024 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Detect Robots
题意翻译
有一张 $n$ 个点的图,给你 $m$ 条路径,每条路径中每个点最多出现一次,如果存在两个点 $A$、$B$,他们在两跳不同的路径中均出现,且在两条路经中 $A$ 到 $B$ 之间的点依次有一个点不同,则输出“Human”,否则输出"Robot"。 数据范围为 $3\times 10^5$。 --- 输入格式:第一行输入t表示有t组数据; 每组数据第一行输入两个整数n,m; 第2~m+1行每行先给出k表示这条路径一共经过k个点,然后输入这k个点 ---- 输出格式:对每组数据每行输出“Human”或"Robot"题目描述
You successfully found poor Arkady near the exit of the station you've perfectly predicted. You sent him home on a taxi and suddenly came up with a question. There are $ n $ crossroads in your city and several bidirectional roads connecting some of them. A taxi ride is a path from some crossroads to another one without passing the same crossroads twice. You have a collection of rides made by one driver and now you wonder if this driver can be a robot or they are definitely a human. You think that the driver can be a robot if for every two crossroads $ a $ and $ b $ the driver always chooses the same path whenever he drives from $ a $ to $ b $ . Note that $ a $ and $ b $ here do not have to be the endpoints of a ride and that the path from $ b $ to $ a $ can be different. On the contrary, if the driver ever has driven two different paths from $ a $ to $ b $ , they are definitely a human. Given the system of roads and the description of all rides available to you, determine if the driver can be a robot or not.输入输出格式
输入格式
Each test contains one or more test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 3 \cdot 10^5 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of crossroads in the city. The next line contains a single integer $ q $ ( $ 1 \le q \le 3 \cdot 10^5 $ ) — the number of rides available to you. Each of the following $ q $ lines starts with a single integer $ k $ ( $ 2 \le k \le n $ ) — the number of crossroads visited by the driver on this ride. It is followed by $ k $ integers $ c_1 $ , $ c_2 $ , ..., $ c_k $ ( $ 1 \le c_i \le n $ ) — the crossroads in the order the driver visited them. It is guaranteed that all crossroads in one ride are distinct. It is guaranteed that the sum of values $ k $ among all rides of all test cases does not exceed $ 3 \cdot 10^5 $ . It is guaranteed that the sum of values $ n $ and the sum of values $ q $ doesn't exceed $ 3 \cdot 10^5 $ among all test cases.
输出格式
Output a single line for each test case. If the driver can be a robot, output "Robot" in a single line. Otherwise, output "Human". You can print each letter in any case (upper or lower).
输入输出样例
输入样例 #1
1
5
2
4 1 2 3 5
3 1 4 3
输出样例 #1
Human
输入样例 #2
1
4
4
3 1 2 3
3 2 3 4
3 3 4 1
3 4 1 2
输出样例 #2
Robot