Pablo Squarson's Headache

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem A: 角角画伯,かく悩みき

角角画伯はキュービズムの大家として知らない人がいるとかいないとか…角角画伯の今年の主題は,正方形だそうです.今日は角角画伯のアトリエにお邪魔しています.

アトリエの中央には途方もなく大きなテーブルがあります.その傍らには同じ大きさに切り揃えられた正方形がたくさん用意されています.角角画伯は一枚の正方形をテーブルの中央に置きました.それに続いて,他の正方形を順番に並べます.その様子を観察すると,画伯の几帳面な性格を反映しているのでしょうか,どの正方形を置くときも,必ず別の正方形に隣接して置き,隣接した正方形の辺をぴたりと揃えているようです.

さあ最初の作品が完成したようです.画伯はごきげんのようです.どうです,この満足そうなお顔は.

あれ?おやおや,今度は画伯は頭を抱えてしまいました.どうしたことでしょう.ははあ.この作品を入れるのにぴったりの箱を注文したいのだけれどもその長さを測るのが大変だと嘆いておられます.さあ,みんなで画伯を手伝ってあげましょう.

画伯が完成させた作品のデータが与えられますので,その幅と高さを出力するプログラムを書いて下さい.正方形の一辺の長さは1とします.画伯が同じ位置に複数の正方形を積み重ねないことを仮定して構いません.

あれあれ,下の図を眺めながら「その十字架はもっと小さい箱に入るんじゃない」なんて言ってる人がいますね.角角画伯は悲しそうな顔で首を振りながら「斜めに入れるような人は自分の画風を理解していない」と言っていますよ.

Input

入力は複数のデータセットからなる.各データセットは,作品の制作手順を表したデータであり,その形式は次の通りである.

N
n1 d1
n2 d2
...
nN-1 dN-1

データセットの最初の行には作品を構成する正方形の数(= N)が与えられる.Nは1以上,200未満の整数である.

データセットの残りの(N-1)行は正方形の置き方を表している.“ni di”は,i (≤ N-1)番の正方形の置き方を指示している.ここで,正方形の番号は,テーブルの上に一番最初に置かれたものを0とし,その後,置いた順番に1, 2, …, (N-1)と番号づけられるものとする.なお0番の正方形に対する置き方の指示はない.

i番の正方形に対する置き方の指示 “ni di” は,i番の正方形をni番の正方形に対してdiで示される方角に隣接して置くことを指示する.ここで,diは0, 1, 2, 3のいずれかをとり,それぞれ左側(= 0),下側 (= 1),右側 (= 2),上側 (= 3)を表す.

例えば以下はSample Inputの四つのデータセットに対応した作品を図示したものである.図中の番号は,正方形の番号に相当する.

入力の終わりはひとつのゼロのみからなる行で表される.

Output

各データセットについて,作品の幅と高さを整数として,それぞれ1行に出力しなさい.幅と高さの間は1文字の空白で区切り,各出力行はこれら以外の文字を含んではならない.

Sample Input

1
5
0 0
0 1
0 2
0 3
12
0 0
1 0
2 0
3 1
4 1
5 1
6 2
7 2
8 2
9 3
10 3
10
0 2
1 2
2 2
3 2
2 1
5 1
6 1
7 1
8 1
0

Output for the Sample Input

1 1
3 3
4 4
5 6

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2010-07-02
http://icpc2010.honiden.nii.ac.jp/