|
||||||||||
CD操作Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 265535/132768 K (Java/Others)Total Submission(s): 6642 Accepted Submission(s): 1974 Problem Description 在Windows下我们可以通过cmd运行DOS的部分功能,其中CD是一条很有意思的命令,通过CD操作,我们可以改变当前目录。 这里我们简化一下问题,假设只有一个根目录,CD操作也只有两种方式: 1. CD 当前目录名\...\目标目录名 (中间可以包含若干目录,保证目标目录通过绝对路径可达) 2. CD .. (返回当前目录的上级目录) 现在给出当前目录和一个目标目录,请问最少需要几次CD操作才能将当前目录变成目标目录? Input 输入数据第一行包含一个整数T(T<=20),表示样例个数; 每个样例首先一行是两个整数N和M(1<=N,M<=100000),表示有N个目录和M个询问; 接下来N-1行每行两个目录名A B(目录名是只含有数字或字母,长度小于40的字符串),表示A的父目录是B。 最后M行每行两个目录名A B,表示询问将当前目录从A变成B最少要多少次CD操作。 数据保证合法,一定存在一个根目录,每个目录都能从根目录访问到。 Output 请输出每次询问的结果,每个查询的输出占一行。 Sample Input
Sample Output
Source | ||||||||||
|