给出一个n 个顶点和 2*(n-1) 条边组成的有向图,对于图上的每条有向边 (u, v) 都存在一条与其相反的边 (v, u)。换句话说这个图由一颗树衍生而出,是把树上的每一条边都被拆成了两条方向相反的边。定义弦为两条相邻的边,且满足其中一条边的终点恰是另一条边的起点。例如对于两条边 (x, y) 和 (y, w),这两条边就是一条弦。边 (u, v) 和边 (v, u) 也是一条弦。若两个弦有公共的边,那就称这两个弦相交,否则为不相交。例如对于两条弦{(a,b),(b,c)} 和 {(b,c),(c,d)} 就是相交的,因为共享了(b,c) 这条边。
显然对于一个由树衍生出的图来说,一定可以把图上所有的边分为n 条互不相交的弦。
现在这个图上因为某些原因缺失了2k 条边,这样就只剩下 m=2(n-1)-2*k 条边了,你能否将图上剩余的边分为 m/2 条互不相交的弦?