P1726 Kamishirasawa Keine

In Gensokyo, Kamishirasawa Keine is a teacher known for her erudition. Due to the Spring Snow incident, many roads in the Human Village area have been blocked by heavy snow, preventing some students from reaching the village where Keine resides. Therefore, Keine decides to choose another village that can gather the largest number of people as the new teaching location. The Human Village area consists of $N$ villages (numbered $1 \cdots N$) and $M$ roads. Roads are of two types: one-way and two-way, denoted by $1$ and $2$, respectively. If there exists a path from village $A$ to village $B$, then we say $A$ can reach $B$, denoted as $(A,B)$. When both $(A,B)$ and $(B,A)$ hold, we say $A$ and $B$ are absolutely connected, denoted as $\langle A,B\rangle$. An absolutely connected region is a set of villages such that any two villages $X, Y$ in the set satisfy $\langle X,Y\rangle$. Your task is to find the largest absolutely connected region and output the villages in this region in increasing order of their indices. If there are multiple largest regions, output the lexicographically smallest one; for example, if $1,3,4$ and $2,5,6$ are two largest regions, output $1,3,4$.

The first line contains two positive integers $N, M$. From line $2$ to line $M+1$, each line contains three positive integers $a, b, t$. If $t = 1$, there is a one-way road from village $a$ to $b$. If $t = 2$, there is a two-way road between villages $a$ and $b$. It is guaranteed that each road appears only once.

On the first line, output $1$ integer, the number of villages in the largest absolutely connected region. On the second line, output several integers, the indices of the villages in the largest absolutely connected region in increasing order, separated by spaces.

- For $60\%$ of the testdata, $1 \le N \le 200$, and $0 \le M \le 10^4$. - For $100\%$ of the testdata, $1 \le N \le 5\times 10^3$, and $0 \le M \le 5\times 10^4$. Translated by ChatGPT 5