TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

85.7% (42/49)

Submission's AC Ratio

48.5% (96/198)

Tags

Description

某校有M種不同的課程,其中有些課程的時間會有衝堂。如果學校中總共有N間不同的教室,請問共有多少種安排各課程上課教室的方式?最少要用到幾間教室?

Input Format

輸入檔案第一列為M值,第二列為N值,M與N皆為小於等於10的正整數。將各課程以編號1到M表示,由第三行起輸入互有衝堂的課程編號配對,兩個課程編號間以空白區分。衝堂的課程編號配對中的編號沒有固定大小順序,例如課程2和課程6出現衝堂,則會有(2, 6)配對或(6, 2)配對,但不會兩者同時出現。

Output Format

第一列輸出共有多少種安排課程上課教室的方式,第二列輸出最少只要用到幾間教室。
若不存在可安排方式則第一列輸出 0種安排方式,第二列輸出至少要用幾間教室才能安排。

Sample Input 1

4
5
1 2
2 3
3 4

Sample Output 1

320
2

Sample Input 2

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

Sample Output 2

0
4

Hints

Problem Source

原TIOJ1197 / TOI2004初選(prob 3)。

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

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