Problem : 295 - The Valley of Mexico

Problem Statistics

Solved Member: 16　　Submission: 74　　User Tried: 16

Statement:

墨西哥城是建立在漂亮的墨西哥山谷上，但是多年前墨西哥山谷卻只是一個大湖。約在西元1300年時，阿茲特克 (Aztec) 的宗教領袖們決定將湖填滿以建立他們王朝的首都。現今，該湖已被完全覆蓋掉了。

在阿茲特克族到來前，該湖的周圍共有c個城市，其中有些城市有相互簽訂貿易協定。市民用船搭載商品至有簽貿易協定的城市進行貿易。任兩個城市之間可以用一條直線穿越該湖相互連結。

有一天，各城的國王共同決定將這些貿易行為給組織化。他們設計了一個可經過所有城市的貿易路線，且該路線符合下列規範：
　　•該路線可從任一城市開始，途中經過所有的城市，最後到達非起始點的城市。
　　•該路線會經過每個城市剛好一次。
　　•路線上每兩個連續的城市必須有簽訂貿易協定。
　　•路線上每兩個連續的城市用直線連接。
　　•為了避免翻船意外，該路線不可自相交叉。

上圖展示該湖及在湖周圍的一些城市。圖中的每一條線（包括粗線與細線）連結簽有貿易協定的兩個城市。此外粗線代表一個起始於城市2，止於城市5的一個貿易路線。

上述貿易路線不會自相交叉。但是如果該路線是從2至6至5至1，則該路線就會自相交叉，因此就不是一個合理的路線。

湖周圍的城市從1至c依順時針方向編號。

Task:

給定城市數c及有簽訂貿易協定的城市組，寫一個程式來找出一條符合上述規定的貿易路線。

Input:Output:

第一行：一整數c (3 ≤ c ≤ 1000)。

第二行：一整數n代表簽有貿易協定的城市組數。

接下來的n行：每一行代表一組貿易協定。每行有兩個用空白隔開的整數，分別代表簽有貿易協定的兩個城市。

數組的測試資料中 3≤c≤20，這幾組的總分為 40 分。

假如確實可以產生合理的貿易路線，就按照路線的順序輸出c行，每一行一個整數。假如無法產生合理的貿易路線，則輸出-1。

附註：假如有許多條合理的貿易路線，字典順序最小的那一組。

Sample Input:Sample Output:

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

2
3
4
1
5
6
7

Source:

IOI 2006

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	30
1-2	1000ms	65536kb
1-3	1000ms	65536kb
1-4	1000ms	65536kb
1-5	1000ms	65536kb
1-6	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-1	1000ms	65536kb	5
3-2	1000ms	65536kb
4-1	1000ms	65536kb	5
4-2	1000ms	65536kb
5-1	1000ms	65536kb	5
5-2	1000ms	65536kb
6	1000ms	65536kb	5
7	1000ms	65536kb	5
8	1000ms	65536kb	5
9	1000ms	65536kb	5
10	1000ms	65536kb	5
11-1	1000ms	65536kb	20
11-2	1000ms	65536kb
11-3	1000ms	65536kb
11-4	1000ms	65536kb