TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

有 n 個幼稚鬼報名參加了組隊比賽。這個比賽的目的是要比看誰能組比較多的隊伍。不限制總共的隊伍數,也不限制每一隊的人數。


這 n 個幼稚鬼之中可能會有某些人彼此討厭對方,因此組隊的時候他們千萬不能被分配在同一隊裡面。還好,大家並沒有討厭彼此到一種很嚴重的程度。我們可以觀察一下會發現,這些人彼此討厭的情況有時候會形成許多小圈圈 (例如:a和b互相討厭,b和c互相討厭,c和d互相討厭,d和a互相討厭),而且 t 個人的小圈圈之中也恰好只有 t 對互相討厭的人。此外,任何兩個小圈圈的交集至多只有一個人。


一場組隊比賽的組隊方式,是這 n 個人以任意形式組隊,只要滿足上述條件。若我們要求每一場比賽的組隊方式都不盡相同(不會有兩場分組方式完全相同的比賽),至多可以辦幾場比賽呢?請輸出答案除以 37493 的餘數。

Input Format

輸入的第一行有一個整數 T (1<=T<=50) 表示有幾組測資。


對於每一筆測試資料,第一行有兩個整數 n, m (1<=n<=500; 0<=m<=n(n-1)/2)。接下來的 m 行每一行有兩個整數 u, v (0<=u, v < n) 表示 u 和 v 彼此討厭對方。這 n 個人的編號是從 0 編到 n-1。

Output Format

對於每一筆測試資料,請輸出組隊的方法數。

Sample Input 1

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

Sample Output 1

5
1
4

Hints

對於第二筆測試資料,只有一種組隊方式,三個人不同隊。

Problem Source

Migrated from old NTUJ.

CF GYM

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 200