#### 457. Snow in Berland

Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Winters are very snowy in Berland, and the current winter is not an exception. Each winter Berland government decides how to clean the roads in the country. The problem is particularly acute in the capital.

You may assume that the capital of Berland consists of n junctions and m one-way roads. Each road has two distinct junctions xi,yi as its end-points, and the traffic goes from xi to yi. There are wi tons of snow on i-th road.

The government hired a private company "Snow White" to clean the city from the snow. Every day the company sends one truck for cleaning the roads — the truck starts from junction A, passes some route to junction B and stops. Single route can contain any road several times, and can pass through any junction (including A and B) several times.

So, the truck makes only one trip from junction A to junction B per day, and the truck's driver, of course, may not violate the traffic direction on the roads. The truck removes one ton of snow from each road it passes. If it passes the road several times during the same day, each time one ton of snow is removed from the road. Because capital residents may decide that the government spends the budget for nothing, the truck can not pass the road if there is no snow on it.

Some roads in the city have historical value due to the presence of government buildings, so this set of roads must be completely cleaned from snow. In other words each road from the specified set should not have snow after "Snow White"'s work. It's known that junction A is situated in the historical center of the capital, meaning that it is possible to reach any historical road from A, walking only along historical roads in the direction of their orientation or in the opposite direction. The direction of roads is not taken into account in this particular case, because we are talking about walking, not driving.

The government pays "Snow White" for each day of work, so "Snow White"'s top managers are looking for a way to work as many days as possible.

Your task is to find the sequence of routes from A to B which doesn't violate the rules described above. This sequence must completely clean all historical roads from snow. Obviously, the sequence should contain as many routes as possible.

Input
 sample input sample output 4 7 1 4 1 2 3 1 2 1 100 0 2 4 1 0 1 3 1 0 3 4 4 0 2 3 2 1 1 4 2 0  6 1 3 4 1 4 1 4 1 2 4 1 2 3 4 1 2 3 4 
 sample input sample output 3 3 1 2 1 3 2 0 3 2 3 0 1 2 1 0  3 1 3 2 1 3 2 1 2