30055 - 【模板】最大团/最大独立集

给定一个无向图 G,你需要对其分别求出:

  • G 的一组最大团。
  • G 的最大团个数。
  • G 的一组最大独立集。
  • G 的最大独立集个数。

G 的最大团为 G 的最大完全子图,完全图为各点间两两均有连边的图。

G 的最大独立集为 G 的最大零子图,零图为各点间两两均没有边的图。

输入

第一行两个正整数 nm,分别表示图 G 的节点个数以及无向边条数。

接下来 m 行,每行两个数 u,v 表示一条无向边连接的两个节点。

图可能会有重边,不会有自环。

输出

第一行两个整数 a,b,分别表示图 G 的最大团大小(即最大团的节点个数)以及最大团个数。

第二行 a 个整数,表示最大团的点集。

第三行两个整数 p,q,分别表示图 G 的最大独立集大小(即最大独立集的节点个数)以及最大独立集个数。

第四行 p 个整数,表示最大独立集的点集。

如果有多个满足要求的点集,输出任意一组即可。

样例

输入

6 7
1 2
2 3
3 4
4 1
3 5
5 4
2 6

输出

3 1
3 4 5
3 2
1 3 6

提示

说明/提示

样例解释

G 的最大团为 {3,4,5}

G 的最大独立集为 {1,3,6}{1,5,6}

数据范围

对于全部数据:1 \leq n \leq 500 \leq m \leq 12251 \leq u,v \leq n

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题