Coupling

Time Limit : 2 sec, Memory Limit : 262144 KB

Problem F: Coupling

Problem

愛津大学では毎年大規模な合コンが行われています。
今年はN人の男性とM人の女性が参加します。
それぞれ男性は0から順にN−1までIDが割り振られおり、女性は0から順にM−1までIDが割り振られています。

この合コンでは自分の「大好きな人」と「そこそこ好きな人」のIDを提示します。
男性はそれぞれ女性のIDを、女性はそれぞれ男性のIDを提示します。

その後、以下のルールに従ってカップルが成立します。

  1. 男性は複数の女性、女性は複数の男性とカップルになってはいけない。
  2. 互いに「大好きな人」と提示した男性と女性でペアができる。
    そこから、任意のペアを選びカップルを作ることができる。
  3. 片方が「大好きな人」、もう片方が「そこそこ好きな人」と提示した男性と女性でペアができる。
    そこから、任意のペアを選びカップルを作ることができる。
  4. 互いに「そこそこ好きな人」と提示した男性と女性でペアができる。
    そこから、任意のペアを選びカップルを作ることができる。
  5. ルール2で出来たカップル、ルール3で出来たカップル、ルール4で出来たカップルの順にカップルの数が最大になるようにカップルが成立する。

サジ君はこの合コンの主催者です。 近年では参加者の数が多くなり手動でカップルの数を把握するのが大変になってきました。そこでプログラマーであるあなたは、サジ君の手伝いをすることにしました。上記のルールに従ってカップルを作った時の「大好きな人」同士のカップルの数と「大好きな人」と「そこそこ好きな人」によるカップルの数と「そこそこ好きな人」同士のカップルの数を出力するプログラムを作成してください。

Input

入力は以下の形式で与えられる。

N M
L1
a1 b1
a2 b2
:
aL1 bL1
L2
c1 d1
c2 d2
:
cL2 dL2
L3
e1 f1
e2 f2
:
eL3 fL3
L4
g1 h1
g2 h2
:
gL4 hL4

1行目にそれぞれ男性の参加者の数と女性の参加者の数を表す2つの整数N,Mが与えられる。次に男性側の大好きな人を表すデータの数L1が与えられる。続くL1行にaibiが空白区切りで与えられる。それぞれ、IDaiの男性がIDbiの女性を「大好き」であることを示す。

続く行に男性側のそこそこ好きな人を表すデータの数L2が与えられる。続くL2行にcidiが空白区切りで与えられる。それぞれ、IDciの男性がIDdiの女性を「そこそこ好き」であることを示す。次に女性側の大好きな人を表すデータの数L3が与えられる。続くL3行にeifiが空白区切りで与えられる。それぞれ、IDeiの女性がIDのfiの男性を「大好き」であることを示す。

続く行に女性側のそこそこ好きな人を表すデータの数L4が与えられる。続くL4行にgihiが空白区切りで与えられる。それぞれ、IDgiの女性がIDhiの男性を「そこそこ好き」であることを示す。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ N,M ≤ 100
  • 0 ≤ ai,ci,fi,hiN−1
  • 0 ≤ bi,di,ei,giM−1
  • 0 ≤ L1,L2,L3,L4 ≤ 2000
  • L1 > 0, L2 > 0 において (ai,bi) ≠ (cj, dj) ( 0 ≤ i < L1, 0 ≤ j < L2 )
  • L3 > 0, L4 > 0 において (ei,fi) ≠ (gj, hj) ( 0 ≤ i < L3, 0 ≤ j < L4 )
  • (ai,bi) ≠ (aj, bj) ( ij ) ( 0 ≤ i < L1, 0 ≤ j < L1 )
  • (ci,di) ≠ (cj, dj) ( ij ) ( 0 ≤ i < L2, 0 ≤ j < L2 )
  • (ei,fi) ≠ (ej, fj) ( ij ) ( 0 ≤ i < L3, 0 ≤ j < L3 )
  • (gi,hi) ≠ (gj, hj) ( ij ) ( 0 ≤ i < L4, 0 ≤ j < L4 )

Output

問題文のルールに従ってカップルが成立した時の、「大好きな人」同士のペアの数と「大好きな人」と「そこそこ好きな人」のペアの数と「そこそこ好き」同士のペアの数を空白区切りで1行に出力せよ。

Sample Input 1

3 3
3
0 0
1 1
2 2
2
1 0
2 1
3
1 1
2 2
0 1
2
1 0
2 0

Sample Output 1

2 0 0

この場合男性1と女性1、男性2と女性2が大好き同士でカップルとなり「大好き同士」のペア数が2になる。 すると、男性0のことが「大好き」な女性も「そこそこ好き」な女性もいなくなってしまいます。 また、女性0のことが「大好き」な男性も「そこそこ好き」な男性もいなくなってしまうため以降カップルは成立しなくなります。

Sample input 2

5 5
5
4 1
2 2
1 4
1 3
4 2
5
1 1
1 2
3 3
3 0
3 4
5
2 3
2 2
0 3
0 2
4 1
5
2 0
4 0
1 0
4 3
2 1

Sample Output2

2 1 0