原題來自：POJ 3417

Dark 是一張無向圖，圖中有 N 個節(jié)點和兩類邊，一類邊被稱為主要邊，而另一類被稱為附加邊。Dark 有 N–1 條主要邊，并且 Dark 的任意兩個節(jié)點之間都存在一條只由主要邊構(gòu)成的路徑。另外，Dark 還有 M 條附加邊。

你的任務(wù)是把 Dark 斬為不連通的兩部分。一開始 Dark 的附加邊都處于無敵狀態(tài)，你只能選擇一條主要邊切斷。一旦你切斷了一條主要邊，Dark 就會進入防御模式，主要邊會變?yōu)闊o敵的而附加邊可以被切斷。但是你的能力只能再切斷 Dark 的一條附加邊。

現(xiàn)在你想要知道，一共有多少種方案可以擊敗 Dark。注意，就算你第一步切斷主要邊之后就已經(jīng)把 Dark 斬為兩截，你也需要切斷一條附加邊才算擊敗了 Dark。

第一行包含兩個整數(shù) N 和 M；

之后 N–1行，每行包括兩個整數(shù) A 和 B，表示 A 和 B 之間有一條主要邊；

之后 M 行以同樣的格式給出附加邊。

數(shù)據(jù)范圍與提示：

對于 20% 的數(shù)據(jù)，1≤N,M≤100；

對于 100% 的數(shù)據(jù)，1≤N≤10⁵,1≤M≤2×10⁵ 。數(shù)據(jù)保證答案不超過 2³¹?1。

信息學(xué)一本通