405031 - 黑白涂色

给一个图上色，要求相邻的结点不能够涂上同样的颜色，一共只有黑色和白色两种颜色，问最多能涂多少黑色结点。例如图5.98中最多能够涂3个黑色结点。

输入的第一行为一个整数N，表示有N组数据，每组数据第一行为两个整数n（n≤100）和k，n为结点数，随后k行为结点数对（n1，n2），n1≠n2。

每组数据输出第一行为一个数字，表示能涂黑色结点的数目，第二行为黑色结点的编号。