Problem : 225 - J. 因式分解

Problem Statistics

Solved Member: 2　　Submission: 23　　User Tried: 3

Statement:

某一天，翰翰在紙上寫了一長串只有加法(or)和乘法(and)的布林變數多項式。無聊的他試著把這個多項式做因式分解，由於翰翰很龜毛，他因式分解有很多要遵守的規則：

1. 只可以使用 '(', ')', '+', '*' 以及變數和常數組成新的多項式表達式
2. 每個變數只可以使用且恰好使用一次
3. 不可以使用常數
4. 每個變數的值都為 0(false) 或 1(true)

他試了好久好久，卻無法成功的分解多項式。因此他希望你幫他寫個程式判斷究竟有沒有可能分解成功，讓他可以少浪費點時間。

例如：

ab + bc 可以分解成 b(a+c)
abc + bc 不可以成功分解
abc + bc + c 不可以成功分解
ab + bc + ca 無法成功的分解

Input:Output:

輸入的第一行有一個正整數 t，代表測資筆數。
每一筆測試資料的第一行有兩個整數 n,m ，代表多項式的長度為 n，共有 m 個變數，這 m 個變數分別由 1 編號到 m。
測試資料的第二行有 n 個整數，這 n 個整數之間以空白和一個符號分隔開來，其中符號有可能是 '*' 或者 '+'，代表翰翰寫的多項式。

限制：
1 ≤ t ≤ 50
1 ≤ n ≤ 5000
1 ≤ m ≤ 80
其中 10% 的測資滿足 m ≤ 5

1 到 m 之間的每個變數在輸入之中至少出現一次

對於每一筆測試資料，請輸出一行。
若有可能成功分解，請輸出 YES。
若否，輸出 NO。

Sample Input:Sample Output:

4
4 2
1 * 2 + 2 * 1
5 3
1 * 2 * 3 + 2 * 3
6 3
1 * 2 * 3 + 2 * 3 + 3
6 3
1 * 2 + 2 * 3 + 3 * 1

YES
NO
NO
NO

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10