🐷大肚肚
CF-22C普及+/提高

割点图

1.0s💾 256MB

📋 题目描述

请你构造一张包含 nn 个顶点( 编号从 11nn ), mm 条边的无向连通图,要求指定的顶点 vv 为图的割点。

📥 输入格式

仅有一行,包含三个整数 n,m,vn,m,v3n1053\le n \le 10^50m1050\le m \le 10^51vn1\le v \le n)。

📤 输出格式

如果无法构造出题目要求的无向图,则输出 1-1 ,否则输出 mm 行,每行包含两个正整数 uiu_iviv_i1ui,vin1\le u_i,v_i\le n ),两数间用一个空格分隔,表示顶点 uiu_i 和顶点 viv_i 之间有一条无向边连接。如果答案不唯一,可以输出任意一种符合要求的方案。

📝 样例 1

输入
5 6 3
输出
1 2
2 3
3 4
4 5
1 3
3 5

📝 样例 2

输入
6 100 1
输出
-1

📚 来源

💡 题目讲解

1

理解题意

给你三个数:nn(顶点数)、mm(边数)、vv(指定的顶点编号)。

你要构造一张无向连通图,要求顶点 vv 是图的割点(articulation point)。

💡 什么叫"割点"? 把割点和它连的边删掉后,图会裂成两块或多块互不连通的部分。

例如下面这张图——顶点 3 就是割点。

造不出来(边太多或太少)就输出 -1。具体多少算多、多少算少,咱们后面慢慢算。

删除顶点 3 之前删除顶点 3 之后123← 割点45无直连1245断开!

绿色圆 = 普通顶点,红色圆 = 割点,橙线 = 连割点,绿线 = 组内互连

1 / 5