蚂蚁_ant

背景

注意看，这个男人叫小帅，他发明了一种机械蚂蚁。

但是现在机械蚂蚁失去控制，过不了多久世界就会毁灭，你能帮助小帅吗？

题目

蚂蚁会已 1m/s 的速度前进，当两只蚂蚁相遇后，两只都会调转方向。当蚂蚁到没有出边的边时，他会调转方向。当走完一条边，会随机选择一条不是刚才走的边。

有一个 $n$ 个点，$m$ 条边的无向图，每条边长 1m，每条边上有无数个蚂蚁，蚂蚁的最初方向不确定。

现在有许多吸管，你可以插到任何一个节点，当蚂蚁经过吸管时，蚂蚁会死掉。

还有 $T$ 秒后，蚂蚁就毁灭世界。请问最坏情况下，最少至少需要几个吸管，才能在 $T$ 秒内消灭所有蚂蚁，并且输出在哪几个节点。

提示

5%：保证图为一条链。

30%：保证图为一棵树

100%：$n\le 10^5,m\le 10^6$