PID635 / 七夕星夜
题目描述

学会了飞翔之术,青青马上便想施展。不料……(此处省略 1000 字)

星星1:此天是我开,此鹊是我栽。要想从此过,把命留下来!

星星2:此天是我开,此鹊是我栽。要想从此过,把命留下来!

星星3:此天是我开,此鹊是我栽。要想从此过,把命留下来!

星星4:……其实……亲……过了我们的迷题就可以了~

星星们出的谜题

随着时间的推移,天上的星星忽明忽暗。在星星亮的时候,如果星星发现他的某一些伙伴同时也亮着,那么就会跟他们发生一种“共鸣”。

例如,如果 a 跟 b 是伙伴,b 跟 c 是伙伴,假如他们现在全亮了,那么 a b c 他们互相之间都会发生共鸣。

更神奇的是,此时如果 b 变暗了,a 跟 c 之间的共鸣仍然会一直持续下去。

像例子中 a、b、c 的关系组成一个“共鸣团”。

现在给出星星们明暗情况与伙伴关系,请回答在整个过程中在同一时刻出现的最大的共鸣团有多少颗星星。

数据规模

对于前 3 个数据,N <= 100, M <= 100

对于后 7 个数据,N <= 200000,M <= 500000

对于所有数据,时间段总数 <= 100000,每颗星星的时间段总数 <= 10。

输入格式

第一行两个数表示星星个数 N 和伙伴关系总数 M。

后接 N 行,表示每个星星的亮暗情况。每行第一个数表示亮暗的时间段数 t,后接 t * 2 个数表示 t 个时间段,s, t 表示此星星在 s 时刻到 t 时刻都是亮着的。

后面 M 行,每行两个数 a, b 表示星星 a 和星星 b 是伙伴。

输出格式

一行一个数表示最大共鸣团中的星星个数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论