Drive Tour

There is a country with N cities (3 <= N <= 256). Some pairs of cities are connected by roads. The cities are numbered from 1 to N, and you start in city 1.

A drive tour starts at city 1, goes to city N, and then returns to city 1. On the way from 1 to N, the city numbers on the route must strictly increase. On the way back from N to 1, the city numbers must strictly decrease. Cities 1 and N may be used in both directions, but every other city may appear in at most one of the two directions.

Given the road information, find a drive tour that visits as many distinct cities as possible.

The first line contains the number of cities N.

Each following line contains two positive integers P and Q describing a road between city P and city Q. Roads are bidirectional, but the actual tour must still satisfy the increasing and decreasing city-number conditions above.

The input ends with a line where P = Q = 0.

If no valid drive tour exists, print 0 on the first line.

Otherwise, print the maximum number of distinct cities visited on the first line. On the second line, print the route as city numbers in order, starting at city 1, reaching city N, and ending back at city 1. If there are multiple optimal routes, any one of them may be printed.