/* graph.h : グラフアルゴリズム関数定義部
Shift-JIS コードに変換して cygwin で compile すると通らないことがある

K. Shiota
2005.5.31 着手
2005.7.15 version
*/

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

/* デフォルトの最大頂点数 */
/* Segmentation fault のエラーが出るときは MAXORDER の値を小さくせよ
  インクルード元でも #define で設定できる */
#ifndef MAXORDER
#define MAXORDER 256	
#endif

#define min(x,y)  ( x < y ? x : y ) 
#define max(x,y)  ( x > y ? x : y ) 

/* グラフを表す構造体の定義 */
/*  ord = 頂点数と、隣接行列 adj[][] で表す */
/* メモリ節約のため隣接行列の成分を char 型に変更 (2005.6.10) */
typedef struct {
	int ord;
	char adj[MAXORDER][MAXORDER];
} Graph;

/********** リスト操作関数定義部 **********/

/* リストを表す構造体の定義 */
/* len = 長さと、メンバー mem[] で表す */
typedef struct {
	int len;
	int mem[MAXORDER];
} List;

/* リスト s 内に k が存在するときは 1、そうでないときは 0 を返す */
int ListMemberQ(int k, List s)
{
	int i;
	for(i=0; i<s.len; i++) if(s.mem[i] == k) return 1;
	return 0;	
}

/* リスト s 内に k が存在するときはその（最初の）ポジション、
   そうでないときは -1 を返す */
int ListPosition(int k, List s)
{
	int i;
	for(i=0; i<s.len; i++) if(s.mem[i] == k) return i;
	return -1;	
}

/* リスト s の最後に k を付け加えたリストを返す */ 
List Append(int k, List s)
{
	List t=s;
	t.mem[s.len]=k;
	t.len=s.len+1;
	return t;
}

/* リスト s の最初に k を付け加えたリストを返す */ 
List Prepend(int k, List s)
{
	List t;
	int i;
	t.len=s.len+1;
	t.mem[0]=k;
	for(i=1;i<t.len;i++) t.mem[i]=s.mem[i-1];
	return t;
}

/* リスト s の後ろにリスト t を結合したリストを返す */ 
List ListAdd(List s, List t)
{
	List u;
	int i;
	u.len=s.len+t.len;
	for(i=0;i<s.len;i++) u.mem[i]=s.mem[i];
	for(i=0;i<t.len;i++) u.mem[s.len+i]=t.mem[i];
	return u;
}

/* 長さ n、全てのメンバー v のリストを返す */ 
List ListInitialize(int n, int v)
{
	List t;
	int i;
	t.len=n;
	for(i=0;i<n;i++) t.mem[i]=v;
	return t;
}

/* リスト s の i 番目から j 番目を抜き出したリストを返す */ 
List SubList(List s, int i, int j)
{
	List t;
	int k;
	t.len=j-i+1;
	if(j<i) t.len=0;
	for(k=0;k<t.len;k++) t.mem[k]=s.mem[i+k];
	return t;
}

/* リスト s の i 番目から j 番目を t に置き換えたリストを返す */ 
List ListReplace(List s, List t, int i, int j)
{
	return ListAdd(ListAdd(SubList(s,0,i-1),t),SubList(s,j+1,s.len-1));
}

/* リスト s の要素を昇順にソートしたリストを返す（バブルソート） */
List Sort(List s)
{
	List t=s;
	int i,j,k,n=s.len;
	for(i=0;i<n;i++)
		for(j=n-1;j>i;j--)
			if(t.mem[j]<t.mem[j-1]){
				k=t.mem[j];
				t.mem[j]=t.mem[j-1];
				t.mem[j-1]=k;
			}
	return t;
}

/* リスト s の要素を逆に並べたリストを返す */
List ListReverse(List s)
{
	List t;
	int i,n=s.len;
	t.len=n;
	for(i=0;i<n;i++) t.mem[i]=s.mem[n-i-1];
	return t;
}

/* リスト s, t の共通メンバーのリストを返す */
List ListCommon(List s, List t)
{
	List u;
	int n=s.len,i,x;
	u.len=0;
	for(i=0;i<n;i++){
		x=s.mem[i];
		if(ListMemberQ(x,t)) u=Append(x,u);
	}
	return u;
}

/* リスト s, t の合併リストを返す */
List ListUnion(List s, List t)
{
	List u=s;
	int n=t.len,i,x;
	for(i=0;i<n;i++){
		x=t.mem[i];
		if(!ListMemberQ(x,s)) u=Append(x,u);
	}
	return u;
}

/* リスト s の全てのメンバーが t に含まれるか否か判定する */
int ListIncludedQ(List s, List t)
{
	int n=s.len,i;
	for(i=0;i<n;i++) if(!ListMemberQ(s.mem[i],t)) return 0;
	return 1;
}

void WriteList(List s)
{
	int i,n=s.len;
	for(i=0;i<n;i++) printf("%d ",s.mem[i]);
	printf("\n");
}

/*********** グラフ入出力関数定義部 **********/

/* 標準入力からグラフを読み込む */
/* 最初に頂点数、続いて順に g.adj[0][0], g.adj[0][1],... */
Graph ReadGraph(void)
{
	int ord,i,j;
	Graph g;
	scanf("%d",&ord);
	g.ord=ord;
	for(i=0;i<ord;i++) for(j=0;j<ord;j++) scanf("%d",&(g.adj[i][j]));
	return g;
}

/* ２次元配列をグラフに読み替える */
Graph ArraytoGraph(int n, int (*m)[n])
{
	Graph g;
	int i,j;
	g.ord=n;
	for(i=0;i<n;i++) for(j=0;j<n;j++) g.adj[i][j]=m[i][j];
	return g;
}

/* グラフの隣接行列を画面表示する */
void WriteGraph(Graph g)
{
	int i,j;
	for(i=0;i<g.ord;i++){
		for(j=0;j<g.ord;j++) printf("%2d",g.adj[i][j]);
		printf("\n");
	}
}

/* 重み付きグラフの隣接行列を画面表示する */
void WriteWeightedGraph(Graph g)
{
	int i,j;
	for(i=0;i<g.ord;i++){
		for(j=0;j<g.ord;j++) printf("%4d",g.adj[i][j]);
		printf("\n");
	}
}

/*********** グラフ演算関数定義部 **********/

/* グラフ g の辺 uv を除去したグラフを返す */
/* 多重辺の場合は1本のみ除去 */
Graph RemoveEdge(Graph g, int u, int v)
{
	Graph h=g;
	h.adj[u][v]--;
	h.adj[v][u]--;
	return h;
}

/* グラフ g からグラフ h の辺を除去したグラフを返す */
/* 多重辺・重み付きの場合は差を計算 */
Graph RemoveEdges(Graph g, Graph h)
{
	Graph k;
	int i,j;
	k.ord=g.ord;
	for(i=0;i<g.ord;i++)
		for(j=0;j<g.ord;j++)
			k.adj[i][j]=g.adj[i][j]-h.adj[i][j];
	return k;
}

/* グラフ g に辺 uv を付加したグラフを返す */
Graph AddEdge(Graph g, int u, int v)
{
	Graph h=g;
	h.adj[u][v]++;
	h.adj[v][u]++;
	return h;
}

/* グラフ g の点 u を除去したグラフを返す */
Graph RemoveVertex(Graph g, int u)
{
	Graph h;
	int i,j;
	h.ord=g.ord-1;
	for(i=0;i<u;i++){
		for(j=i;j<u;j++){
			h.adj[i][j]=g.adj[i][j];
			h.adj[j][i]=g.adj[j][i];
		}
		for(j=u;j<h.ord;j++){
			h.adj[i][j]=g.adj[i][j+1];
			h.adj[j][i]=g.adj[j+1][i];
		}
	}
	for(i=u;i<h.ord;i++){
		for(j=i;j<h.ord;j++){
			h.adj[i][j]=g.adj[i+1][j+1];
			h.adj[j][i]=g.adj[j+1][i+1];
		}
	}	
	return h;
}

/* グラフ g の辺 uv を縮約したグラフを返す */
Graph ContractEdge(Graph g, int u, int v)
{
	Graph h=g;
	int i,j,t;
	if(u>v){ t=u; u=v; v=t; }
	for(i=0;i<h.ord;i++)
		if(i!=u && i!=v){
			h.adj[u][i]=g.adj[u][i]+g.adj[v][i];
			h.adj[i][u]=h.adj[u][i];
		}
	h.adj[u][u]=0;
	h=RemoveVertex(h,v);
	return h;
}

/* グラフ g, h の和を返す */
Graph GraphSum(Graph g, Graph h)
{
	Graph k;
	int i,j;
	k.ord=g.ord+h.ord;
	for(i=0;i<k.ord;i++)
		for(j=0;j<k.ord;j++)
			k.adj[i][j]=0;
	for(i=0;i<g.ord;i++)
		for(j=i;j<g.ord;j++){
			k.adj[i][j]=g.adj[i][j];
			k.adj[j][i]=g.adj[j][i];
		}
	for(i=0;i<h.ord;i++)
		for(j=i;j<h.ord;j++){
			k.adj[g.ord+i][g.ord+j]=h.adj[i][j];
			k.adj[g.ord+j][g.ord+i]=h.adj[j][i];
		}	
	return k;
}

/*********** グラフ生成関数定義部 **********/

/* 頂点数 = n の空グラフを返す */
Graph EmptyGraph(int n)
{
	Graph g;
	int i,j;
	g.ord=n;
	for(i=0;i<n;i++) for(j=0;j<n;j++) g.adj[i][j]=0;
	return g;	
}

/* 頂点数 = n の完全グラフを返す */
Graph CompleteGraph(int n)
{
	Graph g;
	int i,j;
	g.ord=n;
	for(i=0;i<n;i++) for(j=0;j<n;j++) g.adj[i][j]=1;
	for(i=0;i<n;i++) g.adj[i][i]=0;
	return g;	
}

/* 完全二部グラフ K_{m,n} を返す */
Graph CompleteBipartiteGraph(int m, int n)
{
	Graph g;
	int i,j;
	g.ord=m+n;
	for(i=0;i<g.ord;i++) for(j=0;j<g.ord;j++) g.adj[i][j]=0;
	for(i=0;i<m;i++)
		for(j=m;j<g.ord;j++){
			g.adj[i][j]=1;
			g.adj[j][i]=1;
		}
	return g;	
}

/* 頂点数 = n の閉路を返す */
Graph Cycle(int n)
{
	Graph g;
	int i;
	g=EmptyGraph(n);
	for(i=0;i<n;i++){
		g.adj[i][(i+1)%n]=1;
		g.adj[(i+1)%n][i]=1;
	}
	return g;	
}

/* 頂点数 = n の星グラフを返す */
Graph StarGraph(int n)
{
	Graph g;
	int i;
	g=EmptyGraph(n);
	for(i=1;i<n;i++){
		g.adj[0][i]=1;
		g.adj[i][0]=1;
	}
	return g;	
}

/* 頂点数 = n の車輪グラフを返す */
Graph WheelGraph(int n)
{
	Graph g;
	int i;
	g=GraphSum(EmptyGraph(1),Cycle(n-1));
	for(i=1;i<n;i++){
		g.adj[0][i]=1;
		g.adj[i][0]=1;
	}
	return g;	
}

/* k-次元立方体グラフ Qk を返す */
Graph kDimensionalCubicGraph(int k)
{
	Graph g;
	int i,s;
	if(k==0) return EmptyGraph(1);
	else{
		g=kDimensionalCubicGraph(k-1);
		s=g.ord;
		g=GraphSum(g,g);
		for(i=0;i<s;i++){
			g.adj[i][s+i]=1;
			g.adj[s+i][i]=1;
		}
		return g;
	}
}

/* ピータースングラフを返す */
Graph PetersenGraph()
{
	Graph g;
	int i;
	g=EmptyGraph(10);
	for(i=0;i<5;i++){
		g.adj[i][(i+1)%5]=1;
		g.adj[(i+1)%5][i]=1;
	}
	for(i=0;i<5;i++){
		g.adj[5+i][5+(i+2)%5]=1;
		g.adj[5+(i+2)%5][5+i]=1;
	}	
	for(i=0;i<5;i++){
		g.adj[i][5+i]=1;
		g.adj[5+i][i]=1;
	}
	return g;
}

/* ランダムな単純無向グラフを返す */
/* 頂点数 = n, 辺の割合 = rate */
Graph RandomGraph(int n, float rate)
{
	Graph g;
	int i,j;
	float r;

	g=EmptyGraph(n);
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++){
			r=((float)(rand()%10000))/10000;
			if(r<=rate){
				g.adj[i][j]=1;
				g.adj[j][i]=1;
			}
		}
	return g;	
}

/* ランダムな単純無向重みつきグラフを返す */
/* 頂点数 = n, 辺の割合 = rate, 最大重み = m */
/* m<=255 に限定 (2005.6.10) */
Graph RandomWeightedGraph(int n, float rate, int m)
{
	Graph g;
	int i,j,w;
	float r;

	if(m>255){
		printf("最大重みは 255 までにしてください。\n");
		exit(1);
	}
	g=EmptyGraph(n);
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++){
			r=((float)(rand()%10000))/10000;
			if(r<=rate){
				w=rand()%m+1;
				g.adj[i][j]=w;
				g.adj[j][i]=w;
			}
		}
	return g;	
}

/*********** グラフ探索関数定義部 **********/

/* グラフ g を根 r から深さ優先探索する */
/* p : 親を登録するリスト */
/* 返り値は深さ優先探索木 */
Graph DFSTree(Graph g, int r, List *p)
{
	Graph t;	// 最終的に深さ優先探索木を格納して返り値にする
	List cl={0,{}};	// 探索の終わった点のリスト ( closed list )
	int c=r;	// 現在の探索点 ( current node )
	int b;		// 探索木をバックトラック ( backtrack ) するか否か
	int f;		// 連結成分を探索し終わったか否か ( finish )
	int i,j;
	
	t=EmptyGraph(g.ord); 			// 木の初期化
	*p=ListInitialize(g.ord,-1);		// 親が居ないと -1
	cl.mem[cl.len++]=r;			// 根 r は探索済み
	do{
		b=1;
		f=0;
		for(i=0;i<g.ord;i++){
			if(i!=c && g.adj[c][i]>0 && !ListMemberQ(i,cl)){
				// 現在の探索点の隣接点で未探索の点を探し見つかれば
				p->mem[i]=c;		// 親を登録
				t.adj[i][c]=1;		// 探索木の辺を登録
				t.adj[c][i]=1;		// 探索木の辺を登録
				cl.mem[cl.len++]=i;	// 探索済みリストに登録
				c=i;			// 現在点を i に進める
				b=0;			// バックトラックは不要
				break;
			}
		}
		if(b){
			// バックトラックが必要なとき
			// 現在点が r ならこれ以上の探索は不可能
			// そうでなければ探索点の親へ戻る
			if(c==r) f=1;	
			else c=p->mem[c];	
		}
	}while(cl.len!=g.ord && !f);	// 全ての点を探索し終わったか、探索続行不可能で終了
	return t;
}

/* グラフ g を根 r から広さ優先探索する */
/* p : 親 ( parent ) を登録するリスト */
/* 返り値は広さ優先探索木 */
Graph WFSTree(Graph g, int r, List *p)
{
	Graph t;	// 最終的に広さ優先探索木を格納して返り値にする
	List ll;	// 各 node のレベルを登録するリスト
	int c;		// 現在の探索点 ( current node )
	int f;		// 連結成分を探索し終わったか否か ( finish )
	int l=0;	// 現在のレベル
	int i,j;
	
	t=EmptyGraph(g.ord); 			// 木の初期化
	*p=ListInitialize(g.ord,-1);		// 親が居ないと -1
	ll=ListInitialize(g.ord,-1);		// r 以外の点のレベルの初期値は -1
	ll.mem[r]=l;
	do{
		f=1;
		for(c=0;c<g.ord;c++){
			if(ll.mem[c]==l){	// レベル l の点が全て探索点
				for(i=0;i<g.ord;i++){
					if(i!=c && g.adj[c][i]>0 && ll.mem[i]==-1){
					// 現在の探索点の隣接点で未探索の点を探し見つかれば
						p->mem[i]=c;		// 親を登録
						t.adj[i][c]=1;		// 探索木の辺を登録
						t.adj[c][i]=1;		// 探索木の辺を登録
						ll.mem[i]=l+1;		// レベルを l+1 に設定
						f=0;			// 探索続行可能
					}
				}
			}
		}
		l++;				// レベルを +1
	}while(ListMemberQ(-1,ll) && !f);	// 全ての点を探索し終わったか、探索続行不可能で終了
	return t;
}

/*********** グラフ変形関数定義部 **********/

/* Graph g の、部分頂点リスト v から誘導される部分グラフを返す 
   ( v は若い番号順と仮定 ) */
Graph InducedSubGraph(Graph g, List v)
{
	Graph h=g;
	int i;

	for(i=g.ord-1;i>=0;i--)
		if(!ListMemberQ(i,v)) h=RemoveVertex(h,i);
	return h;
}

/* グラフ g から多重辺とループを取り去ったグラフを返す */
Graph SimplifiedGraph(Graph g)
{
	Graph h=g;
	int i,j;

	for(i=0;i<h.ord;i++){
		h.adj[i][i]=0;
		for(j=i+1;j<h.ord;j++)
			if(g.adj[i][j]>0){
				h.adj[i][j]=1;
				h.adj[j][i]=1;
			}
	}
	return h;
}

/*********** 分解 **********/

/* Graph g を連結成分に分解する */
/* 返り値は連結成分の個数 k,
   ni=o->mem[i] は第i連結成分の頂点数
   si=s->mem[i] は n0,...,n{i-1} の積算
   v->.mem[si],...,v->mem[si+ni-1] は第i成分の頂点リスト */
int ConnectedDecompose(Graph g, List *o, List *s, List *v)
{
	Graph t;
	List p;
	int r,i,j,k=0;

	o->len=0;
	s->len=0;
	v->len=0;
	while(v->len<g.ord){
		*s=Append(v->len,*s);		// インデックスを登録
		r=0;
		while(ListMemberQ(r,*v)) r++;	// 未登録点 r を検索
		t=WFSTree(g,r,&p);		// r を根とする広さ優先探索を実行
		i=0;
		for(j=0;j<g.ord;j++)
			if(j==r || p.mem[j]!=-1){	// 根 r と、親のいる点は同じ連結成分
				i++;			// 連結成分内の頂点数
				*v=Append(j,*v);	// 頂点を登録
			}
		*o=Append(i,*o);		// 頂点数を登録
		k++;
	}
	return k;
}

/* 単純無向連結グラフ g をブロックに分解する 
   返り値はブロックの個数 k,
   ni=o->mem[i] は第iブロックの頂点数
   si=s->mem[i] は n0,...,n{i-1} の積算
   v->.mem[si],...,v->mem[si+ni-1] は第iブロックの頂点リスト */
/* Reference: 
   Chartrand-Oellermann,
   Applied and Algorithmic Graph Theory, Alg.3.2 */
int BlockDecompose(Graph g, List *o, List *s, List *v)
{
	Graph sc=g;	// scan した辺を除去してゆく 
	List pr;	// parent
	List lp;	// low point
	List df;	// depth first search index
	List ss;
	List u;
	int c,r,i=0,j,k=0;

	// BlockDecompose_Step1
	pr=ListInitialize(g.ord,-1);
	df=ListInitialize(g.ord,0);
	o->len=0;
	s->len=0;
	v->len=0;
	ss.len=0;

	BlockDecompose_Step2:
	for(j=0;j<g.ord;j++) if(df.mem[j]==0) break;
	if(j>=g.ord) return k;
	else{
		c=j;	// current vertex
		r=j;	// root
	}
	
	BlockDecompose_Step3:
	i++;
	df.mem[c]=i;
	lp.mem[c]=i;
	ss=Prepend(c,ss);

	BlockDecompose_Step4:
	for(j=0;j<g.ord;j++) if(sc.adj[c][j]) break;

	//BlockDecompose_Step5
	if(j<g.ord){
		sc=RemoveEdge(sc,c,j);
		if(df.mem[j]==0){
			pr.mem[j]=c;
			c=j;
			goto BlockDecompose_Step3;
		}
		else{
			// BlockDecompose_Step6
			lp.mem[c]=min(lp.mem[c],df.mem[j]);
			goto BlockDecompose_Step4;
		}
	}
	
	// BlockDecompose_Step7
	if(pr.mem[c]!=r){

		// BlockDecompose_Step8
		if(lp.mem[c]<df.mem[pr.mem[c]]){
			lp.mem[pr.mem[c]]=min(lp.mem[c],lp.mem[pr.mem[c]]);
		}
		else{	
			// BlockDecompose_Step9
			// pr.mem[c] is a cut-vertex
			for(j=0;j<ss.len;j++) if(ss.mem[j]==c) break;	
			u=Append(pr.mem[c],SubList(ss,0,j));	// スタックの c までとカット点を抜き出す
			u=Sort(u);
			*s=Append(v->len,*s);		// インデックスを登録
			*v=ListAdd(*v,u);		// 頂点を登録
			*o=Append(u.len,*o);		// 頂点数を登録
			k++;				// ブロック数を更新
			ss=SubList(ss,j+1,ss.len-1);
		}
		
		// BlockDecompose_Step10
		c=pr.mem[c];
		goto BlockDecompose_Step4;
	}

	// BlockDecompose_Step11
	for(j=0;j<ss.len;j++) if(ss.mem[j]==c) break;	
	u=Append(r,SubList(ss,0,j));	// スタックの c までと root を抜き出す
	u=Sort(u);
	*s=Append(v->len,*s);		// インデックスを登録
	*v=ListAdd(*v,u);		// 頂点を登録
	*o=Append(u.len,*o);		// 頂点数を登録
	k++;				// ブロック数を更新
	ss=SubList(ss,j+1,ss.len-1);
	
	BlockDecompose_Step12:
	for(j=0;j<g.ord;j++) if(sc.adj[r][j]) break;
	if(j<g.ord){
		c=r;
		goto BlockDecompose_Step4;
	}
	else goto BlockDecompose_Step2;
}

/*********** その他 **********/

/* u を根とする探索木の、親を登録したリスト pt から u-v 道を探す */
List ParentPath(List pt, int u, int v)
{
	List p={0,{}};		// 道順（初期値は空）
	int c=v;		// 現在位置

	p=Prepend(c,p);
	do{
		c=pt.mem[c];
		p=Prepend(c,p);	// 親を順に p に前置きしてゆく
	}while(c!=u);		// u に来たら終了
	return p;
}

/* グラフ g で u-v 道を探す 
   u-v 道が存在しなければ返り値は空リスト */
List FindPath(Graph g, int u, int v)
{
	List p={0,{}};		// 道順（初期値は空）
	List pt;
	Graph t=WFSTree(g,u,&pt);
	if(pt.mem[v]!=-1) p=ParentPath(pt,u,v);
	return p;
}

/* 全ての頂点の次数が 2 以上の単純連結無向グラフから閉路をひとつみつける */
List FindCycle(Graph g)
{
	Graph h=g;
	int n=g.ord;
	List p={1,{0}};
	List v=ListInitialize(n,0);
	int c=0,j;
	do{
		v.mem[c]=1;
		for(j=0;j<n;j++)
			if(j!=c && h.adj[c][j]>0){
				h=RemoveEdge(h,c,j);
				c=j;
				p=Append(c,p);
				break;
			}
	}while(!v.mem[c]);
	j=0; while(p.mem[j]!=c) j++;
	return SubList(p,j,p.len-1);
}

/* 頂点数 n のグラフの中の、巡回リスト c で与えられた閉路を返す */
Graph ListtoCycle(int n, List c)
{
	Graph g=EmptyGraph(n);
	int i;
	for(i=0;i<c.len-1;i++) g=AddEdge(g,c.mem[i],c.mem[i+1]);
	return g;
}

/* Graph g の辺数を返す */
/* 無向グラフであれば多重辺、ループがあっても可 */
/* 重みつきグラフなら重み合計 */
int CountEdge(Graph g)
{
	int i,j,s=0;
	for(i=0;i<g.ord;i++) for(j=i;j<g.ord;j++) s+=g.adj[i][j];
	return s;
}

/* Graph g の頂点 v の次数を返す */
int CountDegree(Graph g, int v)
{
	int i,s=g.adj[v][v];
	for(i=0;i<g.ord;i++) s+=g.adj[v][i];
	return s;
}

/* Graph g の次数 1 以上の点のリストを返す */
List PosDegVertices(Graph g)
{
	List s;
	int i;
	s.len=0;
	for(i=0;i<g.ord;i++) if(CountDegree(g,i)>0) s=Append(i,s);
	return s;
}
	
/* Graph g が空グラフであるか否かを判定する */
int EmptyGraphQ(Graph g)
{
	return (CountEdge(g)==0);
}

/* グラフ g の辺 uv が橋であるか否かを判定する */
int BridgeQ(Graph g, int u, int v)
{
	Graph t;
	List p;
	t=WFSTree(RemoveEdge(g,u,v),u,&p);	// g から uv を除去したグラフで u を根とする wfs を実行し
	return (p.mem[v]==-1);			// v に親がいなければ uv は橋
}

/* グラフ g が連結であるか否かを判定する */
int ConnectedQ(Graph g)
{
	Graph t;
	List p;
	int i;
	t=WFSTree(g,0,&p);				// g で 0 を根とする wfs を実行し
	for(i=1;i<g.ord;i++) if(p.mem[i]==-1) return 0;	// 0 以外の或る点に親がいなければ非連結
	return 1;
}

/* グラフ t が木であるか否かを判定する */
int TreeQ(Graph t)
{
	return (ConnectedQ(t) && CountEdge(t)==(t.ord-1));
}

/* グラフ g が閉路を含むか否かを判定する */
int ExistCycleQ(Graph g)
{
	Graph h;		// 連結成分
	List o;			// 連結成分の頂点数のリスト
	List s;			// 連結成分の頂点数インデックスのリスト
	List v;			// 連結成分の頂点のリスト
	int i,j,n,t,k;

	k=ConnectedDecompose(g,&o,&s,&v);
	for(i=0;i<k;i++){
		t=o.mem[i];
		n=s.mem[i];
		h=InducedSubGraph(g,SubList(v,n,n+t-1));
		if(!TreeQ(h)) return 1;
	}
	return 0;
}

/*********** 最小連結子問題 **********/

/* 連結重みつきグラフの最小連結子を返す */
Graph MinSpanningTree(Graph g)
{
	Graph h=g;
	Graph t=EmptyGraph(g.ord);
	int n=g.ord,m,i,j,u,v;
	while(!TreeQ(SimplifiedGraph(t))){
		m=INT_MAX;
		for(i=0;i<n;i++)
			for(j=i+1;j<n;j++)
				// 未使用の重み最小の辺 uv を検索
				if(h.adj[i][j]>0 && h.adj[i][j]<m){
					u=i;
					v=j;
					m=h.adj[i][j];
				}
		//  閉路ができなければ t に uv を付加
		if(!ExistCycleQ(SimplifiedGraph(AddEdge(t,u,v)))){
			t.adj[u][v]=m;
			t.adj[v][u]=m;
		}
		// h から uv を除去
		h.adj[u][v]=0;
		h.adj[u][v]=0;
	}
	return t;
}

/*********** オイラー性 **********/

/* グラフ g がオイラーグラフであるか否かを判定する */
int EulerianGraphQ(Graph g)
{
	int i,j,x;
	if(!ConnectedQ(g)) return 0;	// 連結でなければ偽
	for(i=0;i<g.ord;i++){
		x=0;
		for(j=0;j<g.ord;j++)
			if(j!=i) x+=g.adj[i][j];	// 次数の偶奇にループは無関係
		if(x%2==1) return 0;	// 奇数次数の点があれば偽
	}
	return 1;
}

/* オイラーグラフ g のオイラーサイクルを配列で返す */
/* 返り値は g のサイズ */
/* Fleury のアルゴリズム */
int EulerianCircuit(Graph g, int *ec)
{
	int m=CountEdge(g);	// g のサイズ
	int c=0;		// 現在位置
	Graph h=g;
	int i,k=0,r,t,b;
	
	r=m;
	ec[k++]=c;
	while(r>0){
		t=-1;				// 橋による隣接点登録用変数
		b=0;				// 橋以外の隣接点があれば 1
		for(i=0;i<g.ord;i++){
			if(h.adj[c][i]>0){
				if(!BridgeQ(h,c,i)){	// ci が橋でなければ i へ進む
					h=RemoveEdge(h,c,i);
					r--;
					ec[k++]=i;	// サーキットに i を登録
					c=i;		// 現在位置を i に更新
					b=1;		// 橋以外の隣接点があった
					break;
				}			
				else{
					if(t==-1) t=i;	// ci が橋のときは t=i を仮登録
				}
			}
		}
		if(b==0){
			h=RemoveEdge(h,c,t);
			r--;
			ec[k++]=t;	// サーキットに t を登録
			c=t;		// 現在位置を t に更新
		}
	}
	return m;
}

/* グラフ g が半オイラーグラフであるか否かを判定する */
/* オイラーでない半オイラーのとき真、そうでないとき偽
   奇数次数の２点を ポインタで返す */
int SemiEulerianGraphQ(Graph g, int *u, int *v)
{
	int i,j,x,c=0;
	if(!ConnectedQ(g)) return 0;	// 連結でなければ偽
	for(i=0;i<g.ord;i++){
		x=0;
		for(j=0;j<g.ord;j++)
			if(j!=i) x+=g.adj[i][j];	// 次数の偶奇にループは無関係
		if(x%2==1){
			c++;
			if(c==1) *u=i;
			if(c==2) *v=i;
			if(c>2) return 0;	// 奇数次数の点が３個以上あれば偽
		}
	}
	if(c==0) return 0; else return 1;
}

/* 半オイラーグラフ g の半オイラー歩道を配列で返す */
/* 返り値は g のサイズ
   奇数次数の２点 u,v  は引数で受け取る */
int SemiEulerianWalk(Graph g, int u, int v, int *ew)
{
	int ec[1024],m,i,j;
	
	m=EulerianCircuit(AddEdge(g,u,v),ec);
	for(i=0;i<m;i++)
		if((ec[i]==u && ec[i+1]==v) || (ec[i]==v && ec[i+1]==u)) break;
	if(ec[i]==u){
		for(j=0;j<i;j++) ew[j]=ec[i-j];
		for(j=i;j<m;j++) ew[j]=ec[m+i-j];
	}
	else{
		for(j=i;j<m;j++) ew[j-i]=ec[j+1];
		for(j=0;j<i;j++) ew[m-i+j]=ec[j+1];
	}
	return (m-1);
}

/*********** 最短路問題 **********/

/* 重みつきグラフ g で u から v への最短路 p を求める */
/* 返り値は p の長さ */
int Dijkstra(Graph g, int u, int v, List *p)
{
	List tl;	// 仮ラベル
	List el;	// 永久ラベル
	List nb;	// 探索点の隣接点のリスト
	List pt;	// 親を登録するリスト
	int i,j,k,x,m;
	int c;		// 探索点

	tl=ListInitialize(g.ord,INT_MAX);
	el=ListInitialize(g.ord,-1);
	el.mem[u]=0;
	pt=ListInitialize(g.ord,-1);

	c=u;
	do{
		k=0;
		for(i=0;i<g.ord;i++)
			if(el.mem[i]==-1 && g.adj[c][i]>0)
				nb.mem[k++]=i;	// 探索点の未昇格な隣接点を検索
		nb.len=k;
		for(j=0;j<k;j++){
			i=nb.mem[j];
			x=el.mem[c]+g.adj[c][i];
			if(x<tl.mem[i]){
				tl.mem[i]=x;	// 仮ラベルの更新
				pt.mem[i]=c;	// 仮親を登録
			}

		}
		j=-1;
		m=INT_MAX;
		for(i=0;i<g.ord;i++)
			if(el.mem[i]==-1)
				if(tl.mem[i]<m){
					m=tl.mem[i];
					j=i;	// 仮ラベルが最小な点 j を検索
				}
		if(j>=0){
			el.mem[j]=tl.mem[j];	// j の仮ラベルを永久ラベルに昇格し
			c=j;			// j を次の探索点に
		}
	}while(j>=0 && c!=v);

	if(c==v){
		*p=ParentPath(pt,u,v);
		return el.mem[v];
	}
	else{
		// printf("There is no %d-%d path.\n");
		return -1;
	}
}

/*********** ネットワークフロー **********/

/* ランダムなネットワークを返す */
/* 頂点数 = n, 弧の割合 = rate/2, 最大重み = m ( m<=255 に限定 )
   u = 入口、v = 出口、ループはなし */
Graph RandomNetwork(int n, int u, int v, float rate, int m)
{
	Graph g;
	int i,j;
	float r;

	if(m>255){
		printf("最大重みは 255 までにしてください。\n");
		exit(1);
	}
	g=EmptyGraph(n);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(i!=v && i!=j && j!=u){
				r=((float)(rand()%10000))/10000;
				if(r<=rate) g.adj[i][j]=rand()%m+1;
			}
	return g;	
}

/* ネットワークの最大フロー */
/* 入り口 = u、出口 = v のネットワーク g の最大フローをポインタで返す
   返り値はフローの値 */
int MaxFlow(Graph g, int u, int v, Graph *mf)
{
	Graph r=g;
	Graph t;
	List pr,ph;
	int m,x,i,j,n=g.ord,vl;

	*mf=EmptyGraph(n);
	t=WFSTree(r,u,&pr);
	while(pr.mem[v]!=-1){
		//WriteGraph(r);
		//for(i=0;i<ph.len;i++) printf(" %d",ph.mem[i]);
		//getchar();
		ph=ParentPath(pr,u,v);		// 増大道を探索
		m=INT_MAX;
		for(i=1;i<ph.len;i++){
			x=r.adj[ph.mem[i-1]][ph.mem[i]];
			if(x<m) m=x;		// m = 増大道上の最小重み
		}
		for(i=1;i<ph.len;i++){
			(mf->adj[ph.mem[i-1]][ph.mem[i]])+=m;
			(r.adj[ph.mem[i-1]][ph.mem[i]])-=m;		
			(r.adj[ph.mem[i]][ph.mem[i-1]])+=m;
		}
		t=WFSTree(r,u,&pr);
	}
	for(i=0;i<n;i++)			// プラスマイナスを相殺
		for(j=i+1;j<n;j++)
			if(mf->adj[i][j]>mf->adj[j][i]){
				mf->adj[i][j]-=(mf->adj[j][i]);
				mf->adj[j][i]=0;
			}
			else{
				mf->adj[j][i]-=mf->adj[i][j];
				mf->adj[i][j]=0;
			}
	vl=0;
	for(i=0;i<n;i++) if(i!=u) vl+=mf->adj[u][i];
	return vl;
}