题目描述
学会了飞翔之术,青青马上便想施展。不料……(此处省略 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 是伙伴。
输出格式
一行一个数表示最大共鸣团中的星星个数。
样例输入
样例输出