边的类型

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file edgevar.in Output file 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.

【来源】

原创。