1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #615 Is it a Tree?
* Link: http://uva.onlinejudge.org/external/6/615.pdf
*
* @author Franz Mathauser, Rolf Schirm, Markus Mohr
* @version 1.0, 6/22/2009
*
* Status : Accepted
* Runtime: 0.088
*/

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

class StringTreeMap
{
private HashMap<String, HashSet<String>> map = new HashMap<String,
HashSet<String>>();
private HashSet<String> values = new HashSet<String>();

private void put(String key, String value)
{
// Neues HashSet erstellen, falls kein Eintrag existiert
if(!map.containsKey(key))
map.put(key, new HashSet<String>());

// Wert eintragen
map.get(key).add(value);
values.add(value);
}

private boolean containsValue(String value)
{
return values.contains(value);
}

private Set<String> keySet()
{
return map.keySet();
}

private boolean isElement(String key, String value)
{
if(map.containsKey(key))
return map.get(key).contains(value);
return false;
}
}

public static void main(String...args) throws IOException
{
BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));
StringTreeMap map = new Main().new StringTreeMap();
String[] pairs;
boolean tree = true;
int counter = 0;
Iterator<String> iteratorKeySet;
Iterator<String> iteratorCycle;

while( true)
{
String line = reader.readLine();
pairs = line.replaceAll(" ", " ").split(" ");

if(pairs.length >=2 && pairs[pairs.length-1].equals("-1")
&& pairs[pairs.length-2].equals("-1"))
break;

for(int i=0; i < pairs.length && pairs.length >=2; i+=2)
{
if(pairs[i].equals(pairs[i+1]) &&
!pairs[i].equals("0") && !pairs[i+1].equals("0"))
{
tree = false;
break;
}

if(!map.containsValue(pairs[i+1]))
map.put(pairs[i],pairs[i+1]);
else
{
tree = false;
break;
}
}



if(pairs.length >=2 && pairs[pairs.length-1].equals("0")
&& pairs[pairs.length-2].equals("0"))
{
counter++;

int countRoots = 0;
iteratorKeySet = map.keySet().iterator();
while(iteratorKeySet.hasNext())
{
String key = iteratorKeySet.next();
if(!map.containsValue(key))
countRoots++;
}


if(countRoots > 1)
tree = false;

if(tree)
{
HashSet<String> zyklus = new HashSet<String>();
iteratorKeySet = map.keySet().iterator();

while(iteratorKeySet.hasNext())
{
String key = iteratorKeySet.next();
if(map.containsValue(key)){
zyklus.add(key);
}
}

zyklus.remove("0");
iteratorCycle = zyklus.iterator();
String root = null;
String first;
while(iteratorCycle.hasNext())
{
String value = iteratorCycle.next();
first = value;
while(true){
iteratorKeySet = map.keySet().iterator();
while(iteratorKeySet.hasNext())
{
String key = iteratorKeySet.next();
if(map.isElement(key, value))
{
root = key;
value= key;
break;
}
}

if(root.equals(first))
{
tree = false;
break;
}

if(!zyklus.contains(root))
break;
}
if(!tree)
break;
}

if(!tree)
System.out.println("Case "+counter + " is not
a tree.");
else
System.out.println("Case "+counter + " is a
tree.");
}

else
System.out.println("Case "+counter + " is not a
tree.");

tree=true;
map = new Main().new StringTreeMap();
}
}
}
}