This is a puzzle game to be played by two persons, Alice and Bob. Alice draws an n-vertex convex polygon and numbers its vertices with integers 1,2,...,n in an arbitrary way. Then she draws a number of non-crossing diagonals (the vertices of the polygon are not considered to be crossing points). She keeps the drawing secret and tells Bob the polygon's sides and diagonals, without revealing which are which. Each side or diagonal is speci fied by its endpoints. Bob has to guess the order of the vertices on the border of the polygon. Help him solve the puzzle.
Example
If n = 4 and (1,3), (4,2), (1,2), (4,1), (2,3) are the endpoints of the four sides and one diagonal then
the ordering of the vertices on the border of the polygon is 1, 3, 2, 4 (up-to shifting and reversing).
Problem
Write a program that reads the description of sides and diagonals given to Bob by Alice, computes
the order of vertices on the border of the polygon and writes the result.
The input file contains one or more testcases.
First two lines of each test case contain two integers n and m, such that 3<=n<=10,000 and 0<=m<=n-3. Integer n is the number of vertices of the polygon and integer m is the number of its diagonals, respectively.
Then the 3 to m+n+2th line contains exactly 2(m+n) integers separated by single spaces, specifying all sides and some diagonals of the polygon. Integers on positions 2j-1 and 2j, 1<=j<=m+n, specify the two endpoints of a side or a diagonal. The sides and the diagonals can be given in an arbitrary order. There are no duplicates.
The output should consist of a single line containing a permutation of 1,2,...,n separated by spaces. This sequence corresponds to the numbers of vertices on the border of the polygon; the sequence should always start with vertex number 1 and its second element should be the smaller vertex of the two neighbor vertices of vertex 1.
4 1 1 3 4 2 1 2 4 1 2 3
1 3 2 4
Migrated from old NTUJ.
SWERC2001, Problem E, 算法藝術P.291
| No. | Testdata Range | Score |
|---|