B. Farmers Strike
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the midst of a protest over the difficult conditions faced by farmers, it has been decided to block some roads as a measure of pressure. As the son of a farmer, you have been given the task of developing an algorithm to determine, given an origin city and a destination city, the minimum number of roads to block to make it impossible to get from one city to the other.

Each farmer is able to block one road, so the goal is requiring the minimum number of farmers, allowing the rest to continue working and providing basic resources to the population.

Input

The input consists of a single test case. Each case starts with two integers $$$N$$$ and $$$M$$$, representing the number of cities and roads in the city, respectively. Then follow $$$M$$$ lines, each with two integers $$$A_i$$$ and $$$B_i$$$ between $$$0$$$ and $$$N-1$$$, indicating that there is one road connecting city $$$A_i$$$ to $$$B_i$$$ (and not vice versa). It is guaranteed that there will be at most one road connecting two cities in the same direction. The origin city is city $$$0$$$ and the destination city is city $$$N-1$$$.

  • $$$1 \leq N \leq 160$$$ $$$1 \leq 1,000 \leq M$$$
  • $$$0 \leq A, B \leq N-1$$$
  • $$$A_i \neq B_i$$$ $$$(A_i, B_i) \neq (A_j, B_j)$$$
Output

In the first line you must print a single integer, the minimum number of farmers $$$X$$$ necessary to block the circulation between city $$$0$$$ and city $$$N-1$$$. Next, you must print $$$X$$$ lines, with two integers separated by a space on each line, the two cities $$$A_i$$$ and $$$B_i$$$ joining the road that a farmer will occupy, in the direction from $$$A_i$$$ to $$$B_i$$$. If there are several possible answers, anyone will be accepted. Also, the order in which the roads are printed does not matter.

Example
Input
6 8
0 1
0 2
1 2
2 3
3 4
4 1
3 5
4 5
Output
1
2 3