Petya and the Coins

Time limit6sMemory limit1024 MB

Summary

Given n coins and m pairs of coins that differ in material, find every coin that can be the unique copper one in a valid 3-coloring.

Level: Medium7 of 10
Topics: Graph, Union-find, Divide and conquer
Solved: No attempts yet

Problem

Philatelist Petya went to a shop to buy his dream, a genuine copper coin from the 17th century. The seller showed him $n$ coins from the 17th century in stock. Each coin is made of one of three materials: iron, copper, or bronze. Rust has covered the coins, so it is impossible to tell which material each coin is made of.

To help Petya find the right coin, the seller showed him $m$ pairs of coins, where the two coins in each pair are made of different materials. The seller also said that exactly one of the $n$ coins is made of copper. To get the coveted coin, Petya decided to buy every coin that could be copper, based on the information from the seller.

More formally, Petya buys coin $p$ if and only if it is possible that all coins other than $p$ are made of iron or bronze, coin $p$ is made of copper, and in each of the $m$ pairs announced by the seller, the two coins are made of different materials.

Determine which coins Petya buys.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 3 \cdot 10^6$ , $0 \leq m \leq 3 \cdot 10^6$ ), the number of coins and the number of pairs. Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ( $1 \leq a_i, b_i \leq n$ , $a_i \neq b_i$ ), the numbers of two coins made of different materials. All pairs in the input are distinct.

Output

If the seller made a mistake and no coin can be copper, print 0 (without quotes). Otherwise, print on the first line one integer $x$ , the number of coins Petya buys. On the second line, print $x$ integers $c_i$ ( $1 \leq c_i \leq n$ ) in ascending order, the numbers of the coins Petya buys.

Notes

In the first example, coin 1 can be copper if coins 2 and 3 are iron and coin 4 is bronze. Coin 2 can be copper if coins 1 and 3 are iron and coin 4 is bronze. Coin 3 cannot be copper, because the coins 1, 2, and 4 cannot be made only of iron and bronze. Coin 4 can be copper if coins 2 and 3 are iron and coin 1 is bronze.

In the second example, any coin can be copper if the other coin is made of iron.

In the third example, the seller made a mistake, and no coin can be copper.

Examples4

Example 1
Input
```
4 3
1 2
1 4
4 2
```
Expected output
```
3
1 2 4
```
Example 2
Input
```
2 1
1 2
```
Expected output
```
2
1 2
```
Example 3
Input
```
6 6
1 2
4 5
2 3
5 6
1 3
4 6
```
Expected output
```
0
```

Example 4

Input

Expected output

4
2 3 6 7