import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;

/*This class does the arithmetic of Frieze patterns */

public class Frieze {


    public static int vertexWeight(int[][] TREE,int i,int n) {
	int count=1;
	for(int j=0;j<n-3;++j) {
	    if(TREE[j][0]==i) ++count;
	    if(TREE[j][1]==i) ++count;
	}
	return(count);
    }


    public static int[][] setFrieze(int n,int[][] TREE) {	
	int[][] F=new int[n][4*n];
	for(int i=0;i<=n;++i) F[0][2*i+0]=1;
	for(int i=0;i<=n;++i) F[1][2*i+1]=vertexWeight(TREE,i%n,n);
	for(int j=2;j<n;++j) {
	    for(int i=0;i<n;++i) {
		int nn=2*n;
		int a1=F[j-1][(2*i+j-1)%nn];
		int a2=F[j-1][(2*i+j+1)%nn];
		int b=F[j-2][(2*i+j+0)%nn];
		try{F[j][(2*i+j)%nn]=(a1*a2-1)/b;}
		catch(Exception e) {}
	    }
	}
	return(F);
    }

    public static int[][] setFriezeMod(int n,int m,int[][] TREE) {
	int[][] F=setFrieze(n,TREE);
	for(int i=0;i<n;++i) {
	    for(int j=0;j<4*n;++j) {
		F[i][j]=F[i][j]%m;
	    }
	}
	return(F);
    }

    public static int[][] setFriezeRatio1(int n,int[][] TREE) {
	int[][] F=setFrieze(n,TREE);
	int[][] G=new int[n][4*n];
	int nn=2*n;
	for(int i=1;i<n-2;++i) {
	    for(int j=0;j<4*n;++j) {
		int a=0;
		int b=-1;
		int c=0;
		try {
		   a=F[i-1][(j-1+nn)%nn];
		   b=F[i][j];
		   c=F[i+1][(j+1)%nn];
		   G[i][j]=(a+c)/b;
		}
		catch(Exception e) { }
	    }
	}
	for(int i=n-1;i<n;++i) {
	    for(int j=0;j<4*n;++j) {
		G[i][j]=0;
	    }
	}
	return(G);
    }

    public static int[][] setFriezeRatio2(int n,int[][] TREE) {
	int[][] F=setFrieze(n,TREE);
	int[][] G=new int[n][4*n];
	int nn=2*n;
	for(int i=1;i<n-2;++i) {
	    for(int j=0;j<4*n;++j) {
		int a=0;
		int b=-1;
		int c=0;
		try {
		   a=F[i+1][(j-1+nn)%nn];
		   b=F[i][j];
		   c=F[i-1][(j+1)%nn];
		   G[i][j]=(a+c)/b;
		}
		catch(Exception e) { }
	    }
	}
	for(int i=n-1;i<n;++i) {
	    for(int j=0;j<4*n;++j) {
		G[i][j]=0;
	    }
	}
	return(G);
    }

    
}