11550 - Demanding Dilemma

本題給定所有節點及所有連接節點的邊，請你判斷該組資料是否是一組簡單的無向圖。

一個簡單的無向圖定義為一組有序對 G = (V, E)，其中V為一組非空集合的節點，且E為連接無序對(u, v)的邊，其中u與v屬於V，且u不等於v。在此我們先定義若S為一集合，則 |S| 定義為S的大小(元素個數)。一個關聯矩陣(incidence matrix) M 為一個 |V| x |E| 大小的矩陣，其中若元素M(i, j)為 1 則表示第 j 個邊關聯於第 i 個節點(邊一定關聯於兩個節點)，否則為0表示沒有關聯。

給定一個 n x m 的矩陣，請判斷該矩陣是否為一簡單無向圖G的關聯矩陣，其中G = (V, E)且 |V| = n，|E| = m。

Program Input

輸入資料的第一列為整數 t (1 <= t <= 41)表示測試資料的組數。每組測試資料的第一列為兩個整數 n (1 <= n <= 8), m (0 <= m <= n(n-1)/2)，接下來有 n 列，每列 m 個整數(0或1)，第 i 列的第 j 個元素即為M(i, j)。


Program Output

若該組輸入資料為某個簡單無向圖的關聯矩陣則輸出"Yes"，否則請輸出"No"。


INPUT

3
3 3
1 1 0
0 1 1
1 0 1
3 1
1
1
0
3 3
1 1 0
1 1 1
1 0 0

OUTPUT

Yes
Yes
No

---

原文出處