P16645 [GKS 2018 #C] Fairies and Witches

Pari is a powerful fairy who is fighting to protect Fairyland from evil witches. The witches are becoming more powerful every day, so Pari must use magical sticks to cast a protection spell. She can do this by arranging the sticks to form a convex polygon with non-zero area. However, Pari cannot necessarily use whichever sticks she wants! All of the available sticks in Fairyland are packed together, forming a graph in which the edges are sticks and the nodes are endpoints of one or more sticks. (The sticks never touch each other except at endpoints; they are magical!) Whenever Pari removes a stick to use in her spell, all sticks that were adjacent to that stick (that is, that shared a node with that stick) disappear forever and cannot be used in the future. Pari is wondering how many distinct subsets of sticks can be removed from the graph and used to form a convex polygon with nonzero area. All of the sticks are considered distinct, even sticks that have the same length. Two subsets of sticks are distinct if and only if there is at least one stick that is present in one subset but not the other. As stated above, a subset is only valid if there is a way to remove all of the sticks in that subset from the graph without any of them disappearing.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each case begins with one line containing one integer $N$: the number of nodes in the graph formed by the sticks. Then $N$ lines follow; each contains $N$ integers $L_{i,j}$. The $j$-th value on the $i$-th line represents the length of the stick that has its endpoints at the $i$-th and $j$-th nodes, or 0 if there is no such stick.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of valid subsets, as described above.

In Sample Case #1, the packing graph contains $5$ edges of equal length; representing these by the nodes they connect, these are 1-2, 2-3, 3-4, 4-5, and 5-6. To form a closed polygon, we need at least $3$ sides, but the only way to remove $3$ sticks is to select sticks 1-2, 3-4, and 5-6. In Sample Case #2, the graph contains $3$ sticks, 1-2, 3-4, and 5-6. Note that graph can be disconnected. We can form a triangle with side lengths of $2$, $3$, and $4$. In Sample Case #3, the graph contains $3$ sticks, 1-2, 3-4, and 5-6. But we cannot form a closed polygon using sticks of lengths $1$, $2$ and $4$. In Sample Case #4, we cannot remove more than $1$ stick. ### Limits $1 \le T \le 100$. $0 \le L_{i, j} \le 1000$ for all $i, j$. $L_{i, i} = 0$, for all $i$. $L_{i, j} = L_{j, i}$, for all $i, j$. **Small dataset** $N = 6$. **Large dataset** $6 \le N \le 15$.