CF1054G New Road Network

题目描述

有 $n$ 个点和 $m$ 个集合,需要构造出一棵树使得对于 $1\leq i\leq m$,属于集合 $i$ 的所有点构成一个连通块。如果方案存在输出 `YES` 并给出方案,否则输出 `NO`。

输入格式

第一行一个整数 $T$ 表示数据组数。 每组数据的第一行为两个整数 $n,m$,表示点数和集合数。 接下来 $m$ 行,每行一个长度为 $n$ 的 $01$ 串,表示第 $i$ 个集合的信息。如果第 $i$ 行的第 $j$ 个字符为 $1$ 则表示点 $j$ 属于集合 $i$,为 $0$ 则表示不属于。

输出格式

对于每组测试数据,如果能构造出一组方案,输出 `YES` 和一组合法方案,否则输出 `NO`。

说明/提示

$1\le t,n,m,\sum n,\sum m\le 2000$。