F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Graph Reconstruction

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 706    Accepted Submission(s): 3


Problem Description
Let there be a simple graph with N vertices but we just know the degree of each vertex. Is it possible to reconstruct the graph only by these information?
A simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices. The degree of a vertex is the number of edges that connect to it.
 

Input
There are multiple cases. Each case contains two lines. The first line contains one integer N (2 ¡Ü N ¡Ü 100), the number of vertices in the graph. The second line contains N integers in which the ith item is the degree of ith vertex and each degree is between 0 and N-l(inclusive).
 

Output
If the graph can be uniquely determined by the vertex degree information, output "UNIQUE" in the first line. Then output the graph.
If there are two or more different graphs can induce the same degree for all vertices, output "MULTIPLE" in the first line. Then output two different graphs in the following lines to proof.
If the vertex degree sequence cannot deduce any graph, just output "IMPOSSIBLE". The output format of graph is as follows:
N E
u1 u2 ... uE
v1 v2 ... vE
Where N is the number of vertices and E is the number of edges, and {ui,vi} is the ith edge of the graph. The order of edges and the order of vertices in the edge representation is not important since we would use special judge to verify your answer. The number of each vertex is labeled from 1 to N. See sample output for more detail.
 

Sample Input
1 0 6 5 5 5 4 4 3 6 5 4 4 4 4 3 6 3 4 3 1 2 0
 

Sample Output
UNIQUE 1 0 UNIQUE 6 13 3 3 3 3 3 2 2 2 2 1 1 1 5 2 1 5 4 6 1 5 4 6 5 4 6 4 MULTIPLE 6 12 1 1 1 1 1 5 5 5 6 6 2 2 5 4 3 2 6 4 3 2 4 3 4 3 6 12 1 1 1 1 1 5 5 5 6 6 3 3 5 4 3 2 6 4 3 2 4 3 4 2 IMPOSSIBLE
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-05 14:37:54, Gzip enabled