TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

74.2% (23/31)

Submission's AC Ratio

36.2% (38/105)

Description

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

Input Format

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

Output Format

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

Sample Input

Sample Input #1:

4
5
1 2
2 3
3 4

Sample Input #2:

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

Sample Output

Sample Output #1:

320
2

Sample Output #2:

0
4

Hints

Problem Source

原TIOJ1197 / TOI2004初選(prob 3)。

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144