边的类型

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 edgevar.in 输出文件 edgevar.out

【题目描述】

给出一个有向图G，包含V个顶点和E条边，顶点编号从1到V，按顶点编号顺序进行深度优先搜索。搜索完毕，回答询问，说明边是什么类型的边。

【输入格式】


第一行有2个整数V和E，表示这幅图共有V个顶点和E条边。接下来有E行，每行2个整数a、b，表示顶点a到顶点b之间有边。

下一行有一个整数Q(1<=Q<=1000)，表示询问的个数。接下来有Q行，每行2个整数c、d，询问从c到d的边的类型。


【输出格式】

共Q行，每行回答一个询问，表示边的类型。输出tree edge表示该边为树边，back edge为反向边，forward edge为正向边，cross edge为交叉边。（关于以上边的类型定义请参考《算法导论》）

【样例输入】 

6 7
1 2
1 3
1 4
2 4
4 1
5 3
5 6
4
1 2
4 1
5 3
1 4

【样例输出】 

tree edge
back edge
cross edge
forward edge

【提示】

对于20%的数据，2<=V<=100,1<=E<=1000.

对于100%的数据，2<=V<=100000,1<=E<=20000.

【来源】

原创。