17511번 - Capital 다국어

You are given $N$ cities connected by $M$ roads. Cities are numbered from 1 through $N$, and roads are numbered from 1 through $M$. For each pair of cities, there is a sequence of roads that connects those two cities. Road $i$ has the length $L_i$ kilometre and connects city $A_i$ and city $B_i$ bidirectionally. Every road has a positive length, so $L_i > 0$. Unfortunately, you have forgotten the length of each road.

You observed that, for each road, all people on road $i$ are going from $A_i$ to $B_i$, in a single direction. So, you assumed the hypothesis as follows:

• There is a capital city called $S$.
• People are moving from the capital city to other cities. 
• People try to move in the shortest path. So the length of the shortest path from $S$ to $A_i$ is less than or equal to the length of the shortest path from $S$ to $B_i$.

Can you find the capital city $S$ which meets the criteria when you can assign the length of each road to be any positive real number? You may assume that there is at least one city that meets the criteria.

The first line of the input contains two integers $N$ ($2 \le N \le 500$) and $M$ ($N-1 \le M \le \frac{N(N-1)}{2}$).

In the $i$-th line of next $M$ lines, $A_i$ and $B_i$ are given. ($1 \le A_i,\ B_i \le N$) 

There are no loops or multiple edges. Formally, $A_i \ne B_i$, and $\{A_i,\ B_i\} = \{A_j,\ B_j\} \implies i = j$.

In the first line, print the number of possible capital cities, $K$.

In the second line, print $K$ space-separated integers which denotes all possible cities for the capital, in increasing order.