As we all know, Aryan is a funny guy. He decides t...

Question

As we all know, Aryan is a funny guy. He decides to create fun graphs. For a graph $G$ , he defines fun graph $G'$ of $G$ as follows:

Every vertex $v'$ of $G'$ maps to a non-empty independent set $^{\text{∗}}$ or clique $^{\text{†}}$ in $G$ .
The sets of vertices of $G$ that the vertices of $G'$ map to are pairwise disjoint and combined cover all the vertices of $G$ , i.e., the sets of vertices of $G$ mapped by vertices of $G'$ form a partition of the vertex set of $G$ .
If an edge connects two vertices $v_1'$ and $v_2'$ in $G'$ , then there is an edge between every vertex of $G$ in the set mapped to $v_1'$ and every vertex of $G$ in the set mapped to $v_2'$ .
If an edge does not connect two vertices $v_1'$ and $v_2'$ in $G'$ , then there is not an edge between any vertex of $G$ in the set mapped to $v_1'$ and any vertex of $G$ in the set mapped to $v_2'$ .

As we all know again, Harshith is a superb guy. He decides to use fun graphs to create his own superb graphs. For a graph $G$ , a fun graph $G' '$ is called a superb graph of $G$ if $G' '$ has the minimum number of vertices among all possible fun graphs of $G$ .

Aryan gives Harshith $k$ simple undirected graphs $^{\text{‡}}$ $G_1, G_2,\ldots,G_k$ , all on the same vertex set $V$ . Harshith then wonders if there exist $k$ other graphs $H_1, H_2,\ldots,H_k$ , all on some other vertex set $V'$ such that:

$G_i$ is a superb graph of $H_i$ for all $i\in \{1,2,\ldots,k\}$ .
If a vertex $v\in V$ maps to an independent set of size greater than $1$ in one $G_i, H_i$ ( $1\leq i\leq k$ ) pair, then there exists no pair $G_j, H_j$ ( $1\leq j\leq k, j\neq i$ ) where $v$ maps to a clique of size greater than $1$ .

Help Harshith solve his wonder.

$^{\text{∗}}$ For a graph $G$ , a subset $S$ of vertices is called an independent set if no two vertices of $S$ are connected with an edge.

$^{\text{†}}$ For a graph $G$ , a subset $S$ of vertices is called a clique if every vertex of $S$ is connected to every other vertex of $S$ with an edge.

$^{\text{‡}}$ A graph is a simple undirected graph if its edges are undirected and there are no self-loops or multiple edges between the same pair of vertices.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 100$ ). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ( $1\leq n\leq 300, 1\leq k\leq 10$ ).

Then, there are $k$ graphs described. The first line of each graph description contains a single integer $m$ ( $0\leq m\leq \frac{n\cdot(n-1)}{2}$ ).

Next $m$ lines each contain two space-separated integers $u$ and $v$ ( $1\leq u, v\leq n, u\neq v$ ), denoting that an edge connects vertices $u$ and $v$ .

It is guaranteed that the sum of $m$ over all graphs over all test cases does not exceed $2\cdot 10^5$ , and the sum of $n$ over all test cases does not exceed $300$ .

Output

For each testcase, print "Yes" if there exists $k$ graphs satisfying the conditions; otherwise, "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
InputCopy
3
5 2
3
3 4
5 3
5 1
6
3 5
3 4
1 4
1 2
2 3
4 2
4 3
0
3
3 1
1 4
1 2
4
4 2
4 3
1 2
2 3
3 2
0
3
3 1
3 2
1 2
OutputCopy
Yes
Yes
No

Note

For the first test case, the following are the graphs of $G_1, H_1$ and $G_2, H_2$ such that $G_1$ is superb graph of $H_1$ and $G_2$ is superb graph of $H_2$ .

In each graph, vertex $2$ of $G_i$ corresonds to independent set $\{2\_1, 2\_2\}$ of corresponding $H_i$ and remaining vertices $v\in\{1,3,4,5\}$ of $G_i$ correspond to independent set/clique $\{v\}$ in corresponding $H_i$ (a single vertex set can be considered both an independent set and a clique).

In the third test case, it can be proven that the answer is "No".

中文c++回答。

Answer 1

下面的做法基于这样一个观察：

“超级图”（superb graph） 的定义决定了它一定是被某图所有“模（module）”——也就是完全同邻（true twins）和完全同非邻（false twins）——合并之后得到的最小商图。
因此，给定的 $G_i$ 要能成为某个 $\!H_i$ 的超级图，它本身必须是“无模”（twin‐free）的：如果 $G_i$ 中存在一对不同的顶点 $u,v$ ，使得对于除 $u,v$ 之外的任意顶点 $w$ ，都有 $\bigl(u,w\in E\iff v,w\in E\bigr),$ 那么 $u$ 和 $v$ 在任何可能的 $H_i$ 中也会成为模，从而被合并，导致 $G_i$ 不可能是最小商图。

另一方面，若所有 $G_i$ 都是无模的，那么只要对每个 $i$ 取

H_i = G_i,

此时每个顶点单独成块（大小 1 的块显然既是团又是独立集），就能保证：

$G_i$ 就是 $H_i$ 的最小商图。
因为所有块大小都 = 1，根本不存在“某次是独立集且大小 >1、另一次又是团且大小 >1”这种冲突。

于是问题简化为：检查每个输入图 $G_i$ 是否无模。若有任意一个带模（存在“同邻”或“同非邻”）的 $G_i$ ，答案即为 “No”，否则为 “Yes”。

下面给出基于 C++ 的高效实现，用 bitset 加速模检：

cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n, k;
        cin >> n >> k;
        vector< vector< bitset<300> > > all_bs(k, vector<bitset<300>>(n));
        for(int i = 0; i < k; i++){
            int m;
            cin >> m;
            // 读边并填邻接
            for(int e = 0; e < m; e++){
                int u, v;
                cin >> u >> v;
                --u; --v;
                all_bs[i][u].set(v);
                all_bs[i][v].set(u);
            }
        }

        bool ok = true;
        // 对每个图，检验是否存在一对顶点 u<v 构成 module
        for(int i = 0; i < k && ok; i++){
            auto &bs = all_bs[i];
            for(int u = 0; u < n && ok; u++){
                for(int v = u+1; v < n; v++){
                    // 检查 u,v 除彼此外的邻接是否完全一致
                    // 构造两个 bitset 副本，屏蔽掉对彼此的位
                    bitset<300> bu = bs[u], bv = bs[v];
                    bu.reset(v);
                    bv.reset(u);
                    if(bu == bv){
                        // 找到一对同邻/同非邻
                        ok = false;
                        break;
                    }
                }
            }
        }

        cout << (ok ? "Yes\n" : "No\n");
    }
    return 0;
}

复杂度分析

每个测试中，总共处理 $k$ 个图，每个图最多 $\binom{n}{2}$ 对顶点要比较。
每次比较实际上是对两个 bitset<300>（5~6 个 64 位字）做一次按位异或并全零检查，开销常数非常小。
$n\le300,\ k\le10$ ，总时间足以在几百毫秒内跑完。

As we all know, Aryan is a funny guy. He decides t...

問題

思考

Analyzing block types for graph G

Defining block assignments for G_i

Analyzing blow-up conditions for G_i and H_i

Examining third test for contradiction

Reexamining the third case for consistency

回答

分享這個問答