1. 

/**
* Angewandte Mathematik, SS11
* Problem: 101 - The Blocks Problem
* Link: http://uva.onlinejudge.org/external/1/101.pdf
* @author Sebastian Stumpf
* @author Benjamin Vogt
* @version 1.0, 2011-06-06 08:34:48
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.572
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main
{
static Block[] BLOCKLINE = new Block[25];
static Block[] STATICBLOCKLINE = new Block[25];

public static class Block
{
Block belowMe;
Block overMe;
int value;

Block(int value)
{
this.belowMe = null;
this.overMe = null;
this.value = value;
}

boolean legalMove(Block a, Block b)
{
if(a == b)
{
return false;
}
Block bottomOfA = a;
while(bottomOfA.belowMe != null)
{
bottomOfA = bottomOfA.belowMe;
}
Block bottomOfB = b;
while(bottomOfB.belowMe != null)
{
bottomOfB = bottomOfB.belowMe;
}
if(bottomOfA == bottomOfB)
{
return false;
}
return true;

}
void moveOnto(Block a)
{
if(legalMove(a, this))
{
// if there is no block under a, the position of a on the array has to be deleted
if(a.belowMe == null)
BLOCKLINE[a.value] = null;
// if a wasnt the first element, the reference of a.belowMe to a has to be deleted
else
a.belowMe.overMe = null;
// put all the blocks over this back in the array
Block temp = this.overMe;
while(temp != null)
{
Block temp2 = temp.overMe;
temp.overMe = null;
temp.belowMe = null;
BLOCKLINE[temp.value] = temp;
temp = temp2;
}
// put all the blocks over a back in the array
temp = a.overMe;
while(temp != null)
{
Block temp2 = temp.overMe;
temp.overMe = null;
temp.belowMe = null;
BLOCKLINE[temp.value] = temp;
temp = temp2;
}
// update the references, over this is now a and below a is now this,
// over a is nothing
this.overMe = a;
a.belowMe = this;
a.overMe = null;
}
}

void moveOver(Block a)
{
if(legalMove(a, this))
{
// if there is no block under a, the position of a on the array has to be deleted
if(a.belowMe == null)
BLOCKLINE[a.value] = null;
// if a wasnt the first element, the reference of a.belowMe to a has to be deleted
else
a.belowMe.overMe = null;
// we need the top element of the pile this is part of
Block topOfThis = this;
while(topOfThis.overMe != null)
{
topOfThis = topOfThis.overMe;
}
// put all the blocks over a back in the array
Block temp = a.overMe;
while(temp != null)
{
Block temp2 = temp.overMe;
temp.overMe = null;
temp.belowMe = null;
BLOCKLINE[temp.value] = temp;
temp = temp2;
}
// update the references, over topOfThis is now a and below a is now TopOfThis,
// over a is nothing
topOfThis.overMe = a;
a.belowMe = topOfThis;
a.overMe = null;
}
}

void pileOnto(Block a)
{
if(legalMove(a, this))
{
// if there is no block under a, the position of a on the array has to be deleted
if(a.belowMe == null)
BLOCKLINE[a.value] = null;
// if a wasnt the first element, the reference of a.belowMe to a has to be deleted
else
a.belowMe.overMe = null;
// put all the blocks over this back in the array
Block temp = this.overMe;
while(temp != null)
{
Block temp2 = temp.overMe;
temp.overMe = null;
temp.belowMe = null;
BLOCKLINE[temp.value] = temp;
temp = temp2;
}
// update the references, over this is now a and below a is now this,
// over a is no change
this.overMe = a;
a.belowMe = this;
}
}

void pileOver(Block a)
{
if(legalMove(a, this))
{
// compute bottom block of the pile a is part of
// if there is no block under a, the position of a on the array has to be deleted
if(a.belowMe == null)
BLOCKLINE[a.value] = null;
// if a wasnt the first element, the reference of a.belowMe to a has to be deleted
else
a.belowMe.overMe = null;
// we need the top element of the pile over this
Block topOfThis = this;
while(topOfThis.overMe != null)
{
topOfThis = topOfThis.overMe;
}
// update the references, over this is now a and below a is now this,
// over a is no change
topOfThis.overMe = a;
a.belowMe = topOfThis;
}
}
}

public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(reader.readLine());
for(int i = 0; i < n; ++i)
{
Block temp = new Block(i);
BLOCKLINE[i] = temp;
STATICBLOCKLINE[i] = temp;
}
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
String s1;
while(!(s1 = tokenizer.nextToken()).equals("quit"))
{
int a = Integer.valueOf(tokenizer.nextToken());
String s2 = tokenizer.nextToken();
int b = Integer.valueOf(tokenizer.nextToken());
if(s1.equals("move"))
{
if(s2.equals("onto"))
{
STATICBLOCKLINE[b].moveOnto(STATICBLOCKLINE[a]);
}
else
{
STATICBLOCKLINE[b].moveOver(STATICBLOCKLINE[a]);
}
}
else
{
if(s2.equals("onto"))
{
STATICBLOCKLINE[b].pileOnto(STATICBLOCKLINE[a]);
}
else
{
STATICBLOCKLINE[b].pileOver(STATICBLOCKLINE[a]);
}
}
tokenizer = new StringTokenizer(reader.readLine());
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; ++i)
{
sb.append(i+":");
Block temp = BLOCKLINE[i];
while(temp != null)
{
sb.append(" "+temp.value);
temp = temp.overMe;
}
sb.append("\n");
}
System.out.print(sb.toString());
}
}

/*
25
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
move 0 onto 1
move 14 over 1
move 7 over 1
move 13 over 1
pile 8 over 6
pile 8 over 5
move 22 over 1
move 2 over 9
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 15
pile 14 over 18
move 22 over 12
move 9 onto 11
move 19 over 10
move 7 over 1
move 10 over 1
pile 1 over 6
pile 19 over 5
move 13 over 24
move 0 over 9
move 4 over 9
quit
*/