Problem : 147 - 海綿寶寶之蟹堡餐飲聯盟(2-SAT)

Special Judge

Problem Statistics

Solved Member: 21　　Submission: 211　　User Tried: 26

Statement:

看照片就知道美味蟹堡賣得有多好了...Orz。

蟹堡在這世界上太盛行了，為了維持品質，賣蟹堡的餐廳們決定要一起創一個聯盟。
我們知道世界上總共有n間賣蟹堡的餐廳，每間蟹堡有兩個負責人。
不同餐廳的負責人之間，可能會有仇恨關係。
為了讓聯盟裡面保持清流，聯盟裡面的人都不可以有兩兩仇恨關係存在。
另外，為了保持公平性，每一間餐廳都必須恰有一位代表在聯盟內才行。
現在給你m組兩兩對應的仇恨關係，請你輸出一種方案讓聯盟能夠順利成立。
如果沒有任何合法的成立方式，請輸出-1。

Input:Output:

第一行有兩個數字n, m(1≦n≦8000, 0≦m≦20000)，代表有n間餐廳〈2n位負責人，編號1~2n〉，與m組兩兩對應的仇恨關係。
對於第i間餐廳的兩個負責人編號為2i, 2i-1。
接下來有m行，每行有兩個數字a, b，代表編號a和編號b的兩位負責人有仇恨關係。

請輸出一種可行方案，總共n行，每一個編號佔一行。
如果沒有任何可行方案，請輸出-1。

Sample Input:Sample Output:

3 2
1 3
2 4

1
4
5

HINT:

我愛海綿寶寶>///<

Source:

POI 8 Stage 2

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	250ms	32768kb
1	250ms	32768kb	10
2	250ms	32768kb	10
3	250ms	32768kb	10
4-1	250ms	32768kb	10
4-2	250ms	32768kb
5-1	250ms	32768kb	10
5-2	250ms	32768kb
6-1	250ms	32768kb	10
6-2	250ms	32768kb
7	250ms	32768kb	20
8-1	250ms	32768kb	20
8-2	250ms	32768kb
8-3	250ms	32768kb