模板题,无背景。
时间限制开 300ms 是为了卡部分时间复杂度退化成 或者其他时间复杂度的做法,正常做法不会被卡常。
你需要解决下面的问题:
定义一张图是弦图,当且仅当对于该图任意一个长度大于 的环,都存在一个弦。
现在给定一张 个点 条边的无向图,你需要判断该图是否是一张弦图。
若该图是一张弦图,则你还需要求:
本题有多组数据。
第一行一个整数 表示本题共有 组数据。
对于每组数据:
保证图不存在重边,自环,但不保证图连通。
若该图不是一张弦图,则只输出一行一个字符串 No。
No
否则输出第一行一个字符串 Yes。
Yes
然后一行一个长度为 的序列表示该弦图的任意一个完美消除序列。
然后一行 个整数,分别表示:
4 3 3 1 2 2 3 3 1 6 9 1 2 1 3 2 3 2 4 3 4 3 5 4 5 4 6 5 6 9 14 1 2 1 3 1 4 2 3 2 4 3 4 2 5 3 5 4 5 5 6 3 6 6 7 7 8 7 9 5 5 1 2 1 4 2 3 3 4 3 5
Yes 1 2 3 3 3 1 Yes 1 2 3 4 5 6 3 3 2 Yes 1 2 4 3 5 6 8 7 9 4 4 4 No
对于全部的分数满足 。
特殊的,对于前 个测试点,满足 。该部分占 分。
图不存在重边,自环,但是不保证图连通。