Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tags yet

No tag edit access

I. Tram

time limit per test

2 secondsmemory limit per test

64 megabytesinput

standard inputoutput

standard outputIn a Berland city S*** there is a tram engine house and only one tram. Three people work in the house — the tram driver, the conductor and the head of the engine house. The tram used to leave the engine house every morning and drove along his loop route. The tram needed exactly *c* minutes to complete the route. The head of the engine house controlled the tram’s movement, going outside every *c* minutes when the tram drove by the engine house, and the head left the driver without a bonus if he was even one second late.

It used to be so. Afterwards the Berland Federal Budget gave money to make more tramlines in S***, and, as it sometimes happens, the means were used as it was planned. The tramlines were rebuilt and as a result they turned into a huge network. The previous loop route may have been destroyed. S*** has *n* crossroads and now *m* tramlines that links the pairs of crossroads. The traffic in Berland is one way so the tram can move along each tramline only in one direction. There may be several tramlines between two crossroads, which go same way or opposite ways. Every tramline links two different crossroads and for each crossroad there is at least one outgoing tramline.

So, the tramlines were built but for some reason nobody gave a thought to increasing the number of trams in S***! The tram continued to ride alone but now the driver had an excellent opportunity to get rid of the unending control of the engine house head. For now due to the tramline network he could choose the route freely! Now at every crossroad the driver can arbitrarily choose the way he can go. The tram may even go to the parts of S*** from where it cannot return due to one way traffic. The driver is not afraid of the challenge: at night, when the city is asleep, he can return to the engine house safely, driving along the tramlines in the opposite direction.

The city people were rejoicing for some of the had been waiting for the tram to appear on their streets for several years. However, the driver’s behavior enraged the engine house head. Now he tries to carry out an insidious plan of installing cameras to look after the rebellious tram.

The plan goes as follows. The head of the engine house wants to install cameras at some crossroads, to choose a period of time *t* and every *t* minutes turn away from the favourite TV show to check where the tram is. Also the head of the engine house wants at all moments of time, divisible by *t*, and only at such moments the tram to appear on a crossroad under a camera. There must be a camera on the crossroad by the engine house to prevent possible terrorist attacks on the engine house head. Among all the possible plans the engine house head chooses the plan with the largest possible value of *t* (as he hates being distracted from his favourite TV show but he has to). If such a plan is not unique, pick the plan that requires the minimal possible number of cameras. Find such a plan.

Input

The first line contains integers *n* and *m* (2 ≤ *n*, *m* ≤ 10^{5}) — the number of crossroads and tramlines in S*** respectively. The next *m* lines contain the descriptions of the tramlines in "*u* *v*" format, where *u* is the initial tramline crossroad and *v* is its final crossroad. The crossroads are numbered with integers from 1 to *n*, and the engine house is at the crossroad number 1.

Output

In the first line output the value of *t*. In the next line output the value of *k* — the required number of the cameras. In the next line output space-separated numbers of the crossroads, where the cameras should be installed. Output the numbers in increasing order.

Examples

Input

4 5

1 2

2 3

3 4

4 1

1 4

Output

2

2

1 3

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2017 01:39:49 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|