#P9409. 『STA - R2』交朋友
『STA - R2』交朋友
题目背景
找呀找呀找朋友 找到一个好朋友 敬个礼呀握握手 你是我的好朋友
题目描述
幼儿园开学啦!
在开学前,有的小朋友会准备一个毛绒玩具,可以分享给其他小朋友~
具体的,一共有 天,每天的座位表可以表示成一张无向图。每天有毛绒玩具的小朋友一定会选择一个在这一天和他坐在一起的小朋友,并把毛绒玩具送给他。
但是老师规定,每个人只能有一个毛绒玩具。
在这里,我们认为每天每个人会先送出玩具,再从别人那里接受。
问初始时最多可以有多少小朋友有毛绒玩具。
注意:这意味着一个合法的传递过程中不能出现存在小朋友送不出毛绒玩具或者存在小朋友拥有超过一个毛绒玩具的情况,一个初始局面是合法的当且仅当存在一种合法的传递过程。
输入格式
第一行两个正整数 ,表示天数和小朋友的数量。
后描述 张图,表示每天的座位表:
每个描述的第一行是一个正整数 表示边数。
后 行每行两个正整数 表示图中存在一条无向边 。
输出格式
输出一行答案。
提示
样例解释
样例 1 解释:满足条件的唯一方案为初始毛绒玩具位于 和 。
样例 2 解释:满足条件的一组方案为初始毛绒玩具位于 和 。
数据范围
本题采用捆绑测试。
对于 的数据,,,但是注意 的范围不会同时达到上界。
保证给出的每张图没有重边、自环。