#P1515. Street Directions
Street Directions
题目描述
根据汽车碰撞监测系统(ACM)的数据,大多数致命交通事故发生在双向街道上。为了减少交通事故造成的死亡人数,市长决定将尽可能多的街道改为单向通行。您被聘请来执行这项改造任务,要求改造后从任何一个十字路口出发,驾驶员都能通过某些路线到达其他所有十字路口。
您将获得城市中所有双向街道的列表。每条街道连接两个十字路口,且不穿过其他十字路口。每个十字路口最多连接四条街道,且任意两个十字路口之间最多只有一条街道相连。可能存在仅连接一个十字路口的街道。您可以假设当所有街道都是双向时,驾驶员可以从任意目的地到达其他任意目的地。
输入格式
输入包含多个测试用例。每个用例的第一行包含两个整数和,其中表示十字路口的数量(),表示街道的数量。接下来的行每行包含一条街道连接的两个十字路口编号。十字路口编号从到,每条街道只列出一次(如果出现,则不会出现)。输入以结束。
输出格式
对于每个测试用例:
- 首先输出用例编号(从开始),后跟一个空行
- 然后逐行输出每条街道的定向结果:
- 如果可以改为单向,输出表示从十字路口指向
- 如果不能改为单向,则同时输出和
- 最后输出一个单独的
#
字符作为用例结束标记
注意:可能存在多个满足条件的定向方案,其中任意一个都可以接受。
输入样例
7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
0 0
输出样例
1
1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
2
1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#
题目来源
年北美中东部地区竞赛