#P13097. [FJCPC 2025] 割点
[FJCPC 2025] 割点
题目描述
给定一个正整数 和一个长度为 的 01 序列 ,要求你构造一个 个点的无向简单连通图 ,使得:
-
点 是割点,点 不是割点。
-
对于每个 :
若 ,则点 在图 中是割点;
若 ,则点 在图 中不是割点。
- 图 中各顶点的度数满足:。
如果存在多种可行的图,输出任意一种;如果不存在满足条件的图,则输出 。
简单图的定义为:无重边(即任意一对点之间至多只有一条边)且无自环(即不存在一条边两端点相同)的图。
割点的定义为:删掉该点以及它连的边后,使得图连通块个数增加的点。
输入格式
本题包含多组测试数据。
第一行一个正整数 (),表示测试数据的组数。
对于每组数据:
第一行一个正整数 (),表示图中点的个数。
接下来一个长度为 的 01 串,表示序列 。
保证所有数据的 。
输出格式
对于每组数据:
若无解,输出 ;
若有解,第一行输出 (),表示图的边数。接下来 行,每行输出两个正整数,第 行的两个正整数表示第 条边两个点的编号。若有多种满足题意的图,你可以输出任意一种。
2
4
11
7
11000
-1
6
1 2
1 3
1 4
2 5
2 6
3 7
提示
对于样例一,可以证明不存在满足题意的图。
对于样例二,图如下:
其中点 是割点, 分别为:,符合题意。