ｸﾞﾗﾌの色分けを行うCのｿｰｽについて教えてください｡

http://www.cs.sunysb.edu/~algorith/implement/trick/distrib/trick.c

このﾌﾟﾛｸﾞﾗﾑを利用して地図の色分けができないかと考えいますが､ｸﾞﾗﾌ理論が判っていないため､とっかかりが掴めずに困っています｡

そこで2点教えてください｡
1.以下の入力形式は何を意味するのでしょうか？
4 4
1 2
2 3
3 4
1 4


2.ﾌﾟﾛｸﾞﾗﾑﾌﾛｰの概略

URLはﾀﾞﾐｰでも結構です｡

英語で説明してありますね｡

1行目左はﾉｰﾄﾞの個数

1行目右はﾉｰﾄﾞ間を繋ぐｴｯｼﾞの個数

2行目以降は左の番号を持つﾉｰﾄﾞから右の番号を持つﾉｰﾄﾞへのｴｯｼﾞがあるよ､という定義｡

故にこの場合は4つのﾉｰﾄﾞ間を結ぶ4つのｴｯｼﾞがあり､1-2-3-4-1という順番で輪を描いているｸﾞﾗﾌを定義しているです｡

(C)株式会社はてな