#P1515. Street Directions

Street Directions

题目描述

根据汽车碰撞监测系统(ACM)的数据,大多数致命交通事故发生在双向街道上。为了减少交通事故造成的死亡人数,市长决定将尽可能多的街道改为单向通行。您被聘请来执行这项改造任务,要求改造后从任何一个十字路口出发,驾驶员都能通过某些路线到达其他所有十字路口。

您将获得城市中所有双向街道的列表。每条街道连接两个十字路口,且不穿过其他十字路口。每个十字路口最多连接四条街道,且任意两个十字路口之间最多只有一条街道相连。可能存在仅连接一个十字路口的街道。您可以假设当所有街道都是双向时,驾驶员可以从任意目的地到达其他任意目的地。

输入格式

输入包含多个测试用例。每个用例的第一行包含两个整数nnmm,其中nn表示十字路口的数量(2n10002 \leq n \leq 1000),mm表示街道的数量。接下来的mm行每行包含一条街道连接的两个十字路口编号。十字路口编号从11nn,每条街道只列出一次(如果出现i ji\ j,则不会出现j ij\ i)。输入以n=m=0n = m = 0结束。

输出格式

对于每个测试用例:

  1. 首先输出用例编号(从11开始),后跟一个空行
  2. 然后逐行输出每条街道的定向结果:
    • 如果可以改为单向,输出i ji\ j表示从十字路口ii指向jj
    • 如果不能改为单向,则同时输出i ji\ jj ij\ i
  3. 最后输出一个单独的#字符作为用例结束标记

注意:可能存在多个满足条件的定向方案,其中任意一个都可以接受。

输入样例

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
#

题目来源

19981998年北美中东部地区竞赛