#P1726. 上白泽慧音

上白泽慧音

题目描述

在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。

人间之里由 NN 个村庄(编号为 1N1\cdots N)和 MM 条道路组成,道路分为两种一种为单向通行的,一种为双向通行的,分别用 1122 来标记。如果存在由村庄 AA 到达村庄 BB 的通路,那么我们认为可以从村庄 AA 到达村庄 BB,记为 (A,B)(A,B)。当 (A,B)(A,B)(B,A)(B,A) 同时满足时,我们认为 A,BA,B 是绝对连通的,记为 A,B\langle A,B\rangle。绝对连通区域是指一个村庄的集合,在这个集合中任意两个村庄 X,YX,Y 都满足 X,Y\langle X,Y\rangle。现在你的任务是,找出最大的绝对连通区域,并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的,输出字典序最小的,比如当存在 1,3,41,3,42,5,62,5,6 这两个最大连通区域时,输出的是 1,3,41,3,4

输入格式

第一行共两个正整数 N,MN,M

22 行至第 M+1M+1 行,每行有三个正整数 a,b,ta,b,t。若 t=1t = 1 则表示存在从村庄 aabb 的单向道路,若 t=2t = 2 表示村庄 a,ba,b 之间存在双向通行的道路。保证每条道路只出现一次。

输出格式

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

第二行输出若干个整数,依次输出最大的绝对连通区域所包含的村庄编号。

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

3
1 3 5

提示

  • 对于 60%60\% 的数据,1N2001\le N \le 200,且 0M1040\le M \le 10^4
  • 对于 100%100\% 的数据,1N5×1031\le N \le 5\times 10^3,且 0M5×1040\le M \le 5\times 10^4