#PQJ1681x8374. QOJ 1681_8374

    ID: 2690 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2024 集训

QOJ 1681_8374

试机图(graph) 预览输出 图(graph) 【题目描述】 给出一个n 个点R 条边的无向图,结点从1 开始标号。求一个结点序列S 满足以 下条件:

  1. 序列长度m 大于3
  2. 序列中的结点互不相同
  3. 序列中相邻结点间有连边且S1 和Sm 之间也有连边。
  4. 序列中的点构成的导出子图只有m 条边 【输入格式】 从标准输入读入数据。 输入的第一行包含两个正整数n 和R,分别表示结点数和边数。 接下来的R 行,每行包含两个正整数x 和y,保证1 ≤x, y ≤n,表示x 和y 之间 存在一条无向边。 【输出格式】 输出到标准输出。 输出任意一个满足题目描述中条件的序列。如果不存在请输出no。 【样例1 输入】 5 6 1 1 2 2 1 3 3 2 3 4 4 3 5 5 2 6 4 5 7 【样例1 输出】 2 3 4 5 1 第2 页 共7 页 试机图(graph) 预览输出 【样例2 输入】 4 5 1 1 2 2 2 3 3 3 4 4 4 1 5 1 3 6 【样例2 输出】 no 1 【数据范围】 测试点 N ≤ R ≤ 1-3 10 45 4-5 100 1000 6-7 300 20000 8-10 1000 100000 第3 页 共7 页