TopCoder

Nekosyndrome
かわいいは正義!

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

40.0% (4/10)

Tags

Description

胖胖軍團與其他 N-1 個軍團必頇要共同參加一場於星期六舉辦的大會師活動。

每一個軍團都分別有三位成員 (編號分別由 1 到 3 ),而每一個軍團都必頇推派出一位代表者參加這場活動。

麻煩的是,有些人之間彼此是有「心結」的,

如果某兩個人之間有心結且又恰好都各自被推派出來參加這場大會師的話,他們就會打起來!而使得整場活動變成一片混亂!

為了避免這種事情發生,身為大會主辦人的你,希望能夠知道是否有讓大家都和平不吵架的名單存在。

如果有的話,那麼有機會採取「參加名單由大會決定」的方式來化解產生紛爭的可能性。

現在就請你寫一個程式,來計算出是否有這種和平的組合,如果有的話請輸出最小的那一組方案。

※最小組合的定義:
在所有組合中第 1 個軍團推派出來的人編號最小的那個組合。
如果有多個組合都是推派出第 1 個軍團編號最小的人,再考慮第 2 個軍團推派出來的人編號最小的那個組合…… 以此類推。

Input Format

第一行有兩個整數N、M,代表總共有 N 個軍團必頇參加這個聚會,共有 M組人之間有心結。
N≤16,M≤72
之後有 M 行,每一行有四個整數 Gi1, Pi1, Gi2, Pi2,分別表示:
兩個人 i1、i2,而 G 為所屬的組別、P 為在該組別中的編號。

Ex: 假如有一行是 1 2 2 3 就代表第 1 個軍團的第 2 個人和第 2 個軍團的第 3 個人之間有心結,不能同時列入名單中。

Output Format

請先輸出一行 ”yes” 或 ”no” (皆不含雙引號) 代表有沒有和平、不會吵架的組合存在。
如果存在,則請再輸出 N 行,第 i 行表示第 i 個軍團要推派編號為多少的成員參加活動

Sample Input 1

3 0

Sample Output 1

yes
1
1
1

Sample Input 2

3 4
1 1 2 1
1 1 2 2
2 3 1 1
2 1 3 1

Sample Output 2

yes
2
1
2

Hints

Problem Source

原TIOJ1776 / 99建中校內資訊能力競賽(prob1)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10