主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 H: xry111的航线

问题 H: xry111的航线

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 37  解决: 2
[提交][状态][讨论版]

题目描述

xry111正在研究电离层活动。xry111拥有一架高空无人机,该无人机配备了测量电离层活动的仪器。现有n个机场,m条航线。航线是单向的。xry111的无人机每天早晨从某个机场u出发,飞经一条航线,并测量该航线上的电离层活动情况,降落在另一个机场v。机场v的工作人员会帮xry111进行一些地勤工作,直到晚上无人机再次起飞,同样飞经一条航线,并测量该航线上的电离层活动情况,降落在另一个机场x。第二天早晨无人机再次从x出发。

众所周知,白天和晚上的电离层活动情况是不同的。此外,xry111的航空煤油并不多,需要节约使用。因此,xry111希望规划一条飞行路线,使得无人机对每条航线上的电离层活动情况恰好测2次,且一次在白天一次在晚上。由于在非使用条件下无人机可以方便地拆卸运输,飞行路线可以从任一机场开始,在任一机场结束。

输入

多组数据(最多15组)。

每组数据,第一行是两个用空格分割的整数nm。之后m行,每行2个整数uv,表示存在1条从uv的单向航线。

对于70%的数据,有0<n100
对于100%的数据,有0<n≤10000, 0<m100000, 1u, vn
两个机场之间可能存在多条航线。可能存在从一个机场出发并返回自身的航线。

输出

对于每组数据输出1行。若不存在一条飞行路线满足要求,输出“A Xi Ba”(不含引号)。否则,输出2m个整数,用空格或者制表符分割,表示飞行路线经过的第1, 2, …, 2m条航线的编号。若有多条可行的飞行路线,输出任意一条。

样例输入

3 3
1 2
2 3
3 1
2 2
1 2
2 1

样例输出

2 3 1 2 3 1
A Xi Ba

提示

[提交][状态][讨论版]