村庄选址

题目描述

Y 同学正在研究某片区域的交通网络。该区域由 $N$ 个村庄（编号为 $1 \sim N$）和 $M$ 条道路组成。

这里的道路分为两种：一种是仅限单向通行的，另一种是可以双向通行的。 如果图中存在一条从村庄 $A$ 出发最终抵达村庄 $B$ 的合法路径，那么我们认为可以从村庄 $A$ 到达村庄 $B$。 进一步地，如果从村庄 $A$ 可以到达村庄 $B$，并且从村庄 $B$ 也可以到达村庄 $A$，则称村庄 $A$ 和村庄 $B$ 是绝对连通的。

Y 同学定义一个绝对连通区域为一个村庄的集合，在这个集合中，任意两个不同的村庄都是绝对连通的。

现在的任务是，帮助 Y 同学找出该网络中包含村庄数量最多的绝对连通区域。如果存在多个村庄数量并列最多的绝对连通区域，请输出其中字典序最小的那个。

（注：对于两个大小相同的村庄集合，将它们的编号分别按升序排列后进行逐项比较，第一个出现不同的位置上较小的编号所在的集合字典序更小。例如，集合 $\{1, 3, 4\}$ 的字典序小于集合 $\{2, 5, 6\}$）。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示村庄的数量和道路的数量。

接下来 $M$ 行，每行包含三个正整数 $u, v, t$，用于描述一条道路：

• 若 $t = 1$，表示存在一条从村庄 $u$ 到达村庄 $v$ 的单向道路。
• 若 $t = 2$，表示存在一条连接村庄 $u$ 和村庄 $v$ 的双向道路。

保证输入数据中任意两点间的同一方向道路最多只会被描述一次。

输出格式

第一行输出一个整数，表示最大的绝对连通区域所包含的村庄个数。

第二行按编号升序输出若干个整数，依次表示这个最大绝对连通区域所包含的各个村庄的编号。相邻的整数之间用一个空格隔开。

样例

样例输入 #1

5 5
1 2 1
1 3 2
2 4 2
5 1 2
3 5 1

样例输出 #1

3
1 3 5

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 5000$，$0 \le M \le 5 \times 10^4$，$1 \le u, v \le N$，$t \in \{1, 2\}$。