#P13097. [FJCPC 2025] 割点

    ID: 12747 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>图论2025福建Special Judge构造XCPC

[FJCPC 2025] 割点

题目描述

给定一个正整数 nn 和一个长度为 n2n-2 的 01 序列 a2,a3,,an1a_{2}, a_{3}, \dots, a_{n-1},要求你构造一个 nn 个点的无向简单连通图 GG,使得:

  • 11 是割点,点 nn 不是割点。

  • 对于每个 1<i<n1 < i < n

ai=1a_{i} = 1 ,则点 ii 在图 GG 中是割点;

ai=0a_{i} = 0 ,则点 ii 在图 GG 中不是割点。

  • GG 中各顶点的度数满足:deg1deg2degn\rm{deg}_1\geq \rm{deg}_2\geq\dots\geq \rm{deg}_n

如果存在多种可行的图,输出任意一种;如果不存在满足条件的图,则输出 1-1

简单图的定义为:无重边(即任意一对点之间至多只有一条边)且无自环(即不存在一条边两端点相同)的图。

割点的定义为:删掉该点以及它连的边后,使得图连通块个数增加的点。

输入格式

本题包含多组测试数据。

第一行一个正整数 TT1T5001\leq T\leq 500),表示测试数据的组数。

对于每组数据:

第一行一个正整数 nn4n10004\le n \leq 1000),表示图中点的个数。

接下来一个长度为 n2n - 2 的 01 串,表示序列 a2,a3,,an1a_{2}, a_{3}, \dots, a_{n-1}

保证所有数据的 n2000\sum n\leq 2000

输出格式

对于每组数据:

若无解,输出 1-1

若有解,第一行输出 mm0<mn(n1)20<m\leq \frac{n(n-1)}{2}),表示图的边数。接下来 mm 行,每行输出两个正整数,第 ii 行的两个正整数表示第 ii 条边两个点的编号。若有多种满足题意的图,你可以输出任意一种。

2
4
11
7
11000
-1
6
1 2
1 3
1 4
2 5
2 6
3 7

提示

对于样例一,可以证明不存在满足题意的图。

对于样例二,图如下:

其中点 1,2,31,2,3 是割点,deg1deg7\rm{deg}_1\sim\rm{deg}_7 分别为:3,3,2,1,1,1,13,3,2,1,1,1,1,符合题意。